
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>4.排序算法 · 计算机 ,java , 大数据 基础知识体系</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="hzh">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-toggle-chapters/toggle.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-code/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="5.排序列题.html" />
    
    
    <link rel="prev" href="3.散列表.html" />
    

    
    
    
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        <li class="header">操作系统</li>
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../操作系统/1.基本概述.html">
            
                <a href="../操作系统/1.基本概述.html">
            
                    
                    1.操作系统基本概述
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../操作系统/2.进程管理之进程与线程.html">
            
                <a href="../操作系统/2.进程管理之进程与线程.html">
            
                    
                    2.进程管理之进程与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../操作系统/3.进程管理之处理机调度.html">
            
                <a href="../操作系统/3.进程管理之处理机调度.html">
            
                    
                    3.进程管理之处理机调度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../操作系统/4.进程管理之进程同步.html">
            
                <a href="../操作系统/4.进程管理之进程同步.html">
            
                    
                    4.进程管理之进程同步
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../操作系统/5.内存管理之基本概念.html">
            
                <a href="../操作系统/5.内存管理之基本概念.html">
            
                    
                    5.内存管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../操作系统/6.内存管理之虚拟内存.html">
            
                <a href="../操作系统/6.内存管理之虚拟内存.html">
            
                    
                    6.内存管理之虚拟内存
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../操作系统/7.IO设备管理之基本概念.html">
            
                <a href="../操作系统/7.IO设备管理之基本概念.html">
            
                    
                    7.IO设备管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../操作系统/8.面试题总结一.html">
            
                <a href="../操作系统/8.面试题总结一.html">
            
                    
                    8.面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">计算机网络篇</li>
        
        
    
        <li class="chapter " data-level="2.1" data-path="../计算机网络/1.计算机网络入门基础概念.html">
            
                <a href="../计算机网络/1.计算机网络入门基础概念.html">
            
                    
                    1.计算机网络入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="../计算机网络/2.计算机网络通信基础.html">
            
                <a href="../计算机网络/2.计算机网络通信基础.html">
            
                    
                    2.计算机网络通信入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="../计算机网络/3.数据链路层.html">
            
                <a href="../计算机网络/3.数据链路层.html">
            
                    
                    3.数据链路层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="../计算机网络/4.网络层1.html">
            
                <a href="../计算机网络/4.网络层1.html">
            
                    
                    4.网络层(一)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.5" data-path="../计算机网络/5.网络层2.html">
            
                <a href="../计算机网络/5.网络层2.html">
            
                    
                    5.网络层(二)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.6" data-path="../计算机网络/6.传输层.html">
            
                <a href="../计算机网络/6.传输层.html">
            
                    
                    6.传输层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.7" data-path="../计算机网络/7.应用层.html">
            
                <a href="../计算机网络/7.应用层.html">
            
                    
                    7.应用层(⭐)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.8" data-path="../计算机网络/10.HTTP相关协议.html">
            
                <a href="../计算机网络/10.HTTP相关协议.html">
            
                    
                    8.HTTP相关及发展
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.9" >
            
                <span>
            
                    
                    9.websocket
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="2.10" data-path="../计算机网络/9.面试题二.html">
            
                <a href="../计算机网络/9.面试题二.html">
            
                    
                    面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">数据结构篇</li>
        
        
    
        <li class="chapter " data-level="3.1" data-path="1.图论.html">
            
                <a href="1.图论.html">
            
                    
                    1.图论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="2.图论例题.html">
            
                <a href="2.图论例题.html">
            
                    
                    2.图论例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="3.散列表.html">
            
                <a href="3.散列表.html">
            
                    
                    3.散列表
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="3.4" data-path="4.排序算法.html">
            
                <a href="4.排序算法.html">
            
                    
                    4.排序算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.5" data-path="5.排序列题.html">
            
                <a href="5.排序列题.html">
            
                    
                    5.排序算法例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.6" data-path="6.树论.html">
            
                <a href="6.树论.html">
            
                    
                    6.树论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.7" data-path="7.树论例题.html">
            
                <a href="7.树论例题.html">
            
                    
                    7.树论例题.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.8" data-path="9.模板.html">
            
                <a href="9.模板.html">
            
                    
                    数据结构模板
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">算法篇</li>
        
        
    
        <li class="chapter " data-level="4.1" data-path="../算法/leetCode周赛题解.html">
            
                <a href="../算法/leetCode周赛题解.html">
            
                    
                    leetCode周赛记录
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="../算法/1.时间复杂度.html">
            
                <a href="../算法/1.时间复杂度.html">
            
                    
                    1.时间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.3" data-path="../算法/2.深度优先搜索.html">
            
                <a href="../算法/2.深度优先搜索.html">
            
                    
                    2.深度优先搜索算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.4" data-path="../算法/2.深度优先搜索题目集.html">
            
                <a href="../算法/2.深度优先搜索题目集.html">
            
                    
                    2.深搜题目集
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.5" data-path="../算法/3.广度优先搜索.html">
            
                <a href="../算法/3.广度优先搜索.html">
            
                    
                    3.广度优先搜索算法
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">JVM篇</li>
        
        
    
        <li class="chapter " data-level="5.1" data-path="../jvm/1.jvm内存结构.html">
            
                <a href="../jvm/1.jvm内存结构.html">
            
                    
                    1.jvm内存结构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                <a href="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                    
                    2.HotSpot虚拟机对象探秘.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.3" data-path="../jvm/3.对象存亡与垃圾收集算法.html">
            
                <a href="../jvm/3.对象存亡与垃圾收集算法.html">
            
                    
                    3.对象存亡与垃圾收集算法.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.4" data-path="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                <a href="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                    
                    4.HotSpot的算法细节与垃圾收集器.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.5" data-path="../jvm/5.内存分配与回收策略.html">
            
                <a href="../jvm/5.内存分配与回收策略.html">
            
                    
                    5.内存分配与回收策略.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.6" data-path="../jvm/6.类文件结构.html">
            
                <a href="../jvm/6.类文件结构.html">
            
                    
                    6.类文件结构.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.7" data-path="../jvm/7.类加载机制.html">
            
                <a href="../jvm/7.类加载机制.html">
            
                    
                    7.类加载机制.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.8" data-path="../jvm/8.jvm逃逸分析.html">
            
                <a href="../jvm/8.jvm逃逸分析.html">
            
                    
                    8.逃逸分析技术
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">多线程篇</li>
        
        
    
        <li class="chapter " data-level="6.1" data-path="../多线程/basic/0.多线程路线图.html">
            
                <a href="../多线程/basic/0.多线程路线图.html">
            
                    
                    1.多线程学习路线图
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="../多线程/basic/0.java内存模型与线程.html">
            
                <a href="../多线程/basic/0.java内存模型与线程.html">
            
                    
                    2.java内存模型与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="../多线程/3.并行程序基础.html">
            
                <a href="../多线程/3.并行程序基础.html">
            
                    
                    2.并行程序基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                <a href="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                    
                    3.happenBefore与jvm指令重排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="../多线程/basic/1.synchronized与volatile.html">
            
                <a href="../多线程/basic/1.synchronized与volatile.html">
            
                    
                    4.synchronized与volatile.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="../多线程/basic/2.ThreadLocal.html">
            
                <a href="../多线程/basic/2.ThreadLocal.html">
            
                    
                    5.ThreadLocal.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="../多线程/cas/1.乐观锁与悲观锁.html">
            
                <a href="../多线程/cas/1.乐观锁与悲观锁.html">
            
                    
                    6.乐观锁与悲观锁.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="../多线程/cas/2.CAS与atomic类.html">
            
                <a href="../多线程/cas/2.CAS与atomic类.html">
            
                    
                    7.CAS与atomic类.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.9" data-path="../多线程/aqs/1.AQS.html">
            
                <a href="../多线程/aqs/1.AQS.html">
            
                    
                    8.AQS.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.10" data-path="../多线程/aqs/2.基于AQS的并发工具.html">
            
                <a href="../多线程/aqs/2.基于AQS的并发工具.html">
            
                    
                    9.基于AQS的并发工具.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.11" data-path="../多线程/blockingQueue/1.阻塞队列.html">
            
                <a href="../多线程/blockingQueue/1.阻塞队列.html">
            
                    
                    10.阻塞队列.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.12" data-path="../多线程/pond/1.线程池与底层原理.html">
            
                <a href="../多线程/pond/1.线程池与底层原理.html">
            
                    
                    11.线程池与底层原理.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.13" data-path="../多线程/10面试题一.html">
            
                <a href="../多线程/10面试题一.html">
            
                    
                    12.面试题一
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.14" data-path="../多线程/10面试题二.html">
            
                <a href="../多线程/10面试题二.html">
            
                    
                    13.面试题二.md
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">java集合篇</li>
        
        
    
        <li class="chapter " data-level="7.1" data-path="../basic/collection/1.java集合.html">
            
                <a href="../basic/collection/1.java集合.html">
            
                    
                    1.集合架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="../basic/collection/2.HashMap源码分析.html">
            
                <a href="../basic/collection/2.HashMap源码分析.html">
            
                    
                    2.hashMap底层原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.3" data-path="../basic/collection/3.ConcurrentHashMap分析.html">
            
                <a href="../basic/collection/3.ConcurrentHashMap分析.html">
            
                    
                    3.ConcurrentHashMap分析
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">设计模式篇</li>
        
        
    
        <li class="chapter " data-level="8.1" >
            
                <span>
            
                    
                    1.创造型模式
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="8.2" data-path="../设计模式/factory/三种工厂模式介绍.html">
            
                <a href="../设计模式/factory/三种工厂模式介绍.html">
            
                    
                    三种工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.3" data-path="../设计模式/factory/实战工厂模式.html">
            
                <a href="../设计模式/factory/实战工厂模式.html">
            
                    
                    实战工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.4" data-path="../设计模式/factory/实战抽象工厂模式.html">
            
                <a href="../设计模式/factory/实战抽象工厂模式.html">
            
                    
                    实战抽象工厂模式
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">mysql篇</li>
        
        
    
        <li class="chapter " data-level="9.1" data-path="../数据库/mysql/1.b树b+树的底层原理.html">
            
                <a href="../数据库/mysql/1.b树b+树的底层原理.html">
            
                    
                    1.mysql索引基础之b树与b+树⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.2" data-path="../数据库/mysql/2.mysql索引.html">
            
                <a href="../数据库/mysql/2.mysql索引.html">
            
                    
                    2.mysql索引及优化⭐⭐⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.3" data-path="../数据库/mysql/3.mysql存储引擎.html">
            
                <a href="../数据库/mysql/3.mysql存储引擎.html">
            
                    
                    3.mysql存储引擎.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.4" data-path="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                <a href="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                    
                    4.多版本并发控制之mvcc原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.5" data-path="../数据库/mysql/4.mysql事务.html">
            
                <a href="../数据库/mysql/4.mysql事务.html">
            
                    
                    5.mysql事务
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.6" data-path="../数据库/mysql/5.mysql锁机制.html">
            
                <a href="../数据库/mysql/5.mysql锁机制.html">
            
                    
                    6.mysql的锁机制
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.7" data-path="../数据库/mysql/6.mysql面试题一.html">
            
                <a href="../数据库/mysql/6.mysql面试题一.html">
            
                    
                    7.mysql面试题一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高并发中间件篇</li>
        
        
    

    
        
        <li class="header">架构理论篇</li>
        
        
    
        <li class="chapter " data-level="11.1" data-path="../架构/0.架构演进.html">
            
                <a href="../架构/0.架构演进.html">
            
                    
                    1.架构演进
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="11.2" data-path="../架构/0.微服务架构与soa架构.html">
            
                <a href="../架构/0.微服务架构与soa架构.html">
            
                    
                    2.微服务架构与soa架构
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高可用系统篇</li>
        
        
    
        <li class="chapter " data-level="12.1" data-path="../高可用架构/1.限流.html">
            
                <a href="../高可用架构/1.限流.html">
            
                    
                    1.系统限流
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.2" data-path="../高可用系统/2.服务熔断.html">
            
                <a href="../高可用系统/2.服务熔断.html">
            
                    
                    2.服务熔断
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.3" data-path="../高可用系统/3.服务降级.html">
            
                <a href="../高可用系统/3.服务降级.html">
            
                    
                    3.服务降级
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">spring-cloud 微服务篇</li>
        
        
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >4.排序算法</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><ul><ul><li><span class="title-icon "></span><a href="#1&#x5FEB;&#x901F;&#x6392;&#x5E8F;"><b></b>1.&#x5FEB;&#x901F;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><b></b>2.&#x5F52;&#x5E76;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><b></b>3.&#x9009;&#x62E9;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#4&#x5806;&#x6392;&#x5E8F;"><b></b>4.&#x5806;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><b></b>5.&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#6&#x8BA1;&#x6570;&#x6392;&#x5E8F;"><b></b>6.&#x8BA1;&#x6570;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#7&#x57FA;&#x6570;&#x6392;&#x5E8F;"><b></b>7.&#x57FA;&#x6570;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#8&#x6876;&#x6392;&#x5E8F;"><b></b>8.&#x6876;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#9&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;"><b></b>9.&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;</a></li><li><span class="title-icon "></span><a href="#10&#x603B;&#x7ED3;"><b></b>10.&#x603B;&#x7ED3;</a></li></ul></ul></ul></div><a href="#" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h3 id="1&#x5FEB;&#x901F;&#x6392;&#x5E8F;"><a name="1&#x5FEB;&#x901F;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#1&#x5FEB;&#x901F;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5FEB;&#x901F;&#x6392;&#x5E8F;" class="plugin-anchor" href="#1&#x5FEB;&#x901F;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5FEB;&#x901F;&#x6392;&#x5E8F;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130141224.gif" alt=""></p>
<p>&#x57FA;&#x672C;&#x601D;&#x60F3;&#x662F;&#xFF1A;&#x901A;&#x8FC7;&#x4E00;&#x8D9F;&#x6392;&#x5E8F;&#x5C06;&#x8981;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x636E;&#x5206;&#x5272;&#x6210;&#x72EC;&#x7ACB;&#x7684;&#x4E24;&#x90E8;&#x5206;&#xFF0C;&#x5176;&#x4E2D;&#x4E00;&#x90E8;&#x5206;&#x7684;&#x6240;&#x6709;&#x6570;&#x636E;&#x90FD;&#x6BD4;&#x53E6;&#x5916;&#x4E00;&#x90E8;&#x5206;&#x7684;&#x6240;&#x6709;&#x6570;&#x636E;&#x90FD;&#x8981;&#x5C0F;&#xFF0C;&#x7136;&#x540E;&#x518D;&#x6309;&#x6B64;&#x65B9;&#x6CD5;&#x5BF9;&#x8FD9;&#x4E24;&#x90E8;&#x5206;&#x6570;&#x636E;&#x5206;&#x522B;&#x8FDB;&#x884C;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#xFF0C;&#x6574;&#x4E2A;&#x6392;&#x5E8F;&#x8FC7;&#x7A0B;&#x53EF;&#x4EE5;&#x9012;&#x5F52;&#x8FDB;&#x884C;&#xFF0C;&#x4EE5;&#x6B64;&#x8FBE;&#x5230;&#x6574;&#x4E2A;&#x6570;&#x636E;&#x53D8;&#x6210;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x3002;</p>
<p>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;: <a href="https://private.codecogs.com/gif.latex?O(n*logn" target="_blank"><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130142239.gif" alt="O(n*logn)"></a>) &#x3002;</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">quick_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; &amp; arr, <span class="hljs-keyword">int</span> start ,<span class="hljs-keyword">int</span> end)</span></span>{
    <span class="hljs-keyword">if</span> ( start&lt;end ){
        <span class="hljs-keyword">int</span> left = start;
        <span class="hljs-keyword">int</span> right = end;
        <span class="hljs-keyword">int</span> pivot= arr[start];
        <span class="hljs-keyword">while</span> (left&lt;right){
            <span class="hljs-keyword">while</span>(left&lt;right&amp;&amp;arr[right]&gt;=pivot)right--;
            arr[left]=arr[right];
            <span class="hljs-keyword">while</span>(left&lt;right&amp;&amp;arr[left]&lt;=pivot)left++;
            arr[right]=arr[left];
        }
        arr[left]=pivot;
        quick_sort( arr , start,left<span class="hljs-number">-1</span>);
        quick_sort( arr ,left+<span class="hljs-number">1</span>,end);
    }
}
</code></pre>
<p><strong>&#x590D;&#x6742;&#x5EA6;&#x5206;&#x6790;</strong></p>
<p>&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x6D89;&#x53CA;&#x5230;&#x9012;&#x5F52;&#x8C03;&#x7528;&#xFF0C;&#x6240;&#x4EE5;&#x8BE5;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x8FD8;&#x9700;&#x8981;&#x4ECE;&#x9012;&#x5F52;&#x7B97;&#x6CD5;&#x7684;&#x590D;&#x6742;&#x5EA6;&#x5F00;&#x59CB;&#x8BF4;&#x8D77;&#xFF1B;</p>
<p>&#x200B;    <strong>&#x9012;&#x5F52;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x516C;&#x5F0F;&#xFF1A;T[n] = aT[n/b] + f(n)  &#xFF1B;</strong>&#x5BF9;&#x4E8E;&#x9012;&#x5F52;&#x7B97;&#x6CD5;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x8FD9;&#x91CC;&#x5C31;&#x4E0D;&#x5C55;&#x5F00;&#x6765;&#x8BF4;&#x4E86;&#xFF1B;</p>
<p><strong>&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x6700;&#x4F18;&#x7684;&#x60C5;&#x51B5;&#x5C31;&#x662F;&#x6BCF;&#x4E00;&#x6B21;&#x53D6;&#x5230;&#x7684;&#x5143;&#x7D20;&#x90FD;&#x521A;&#x597D;&#x5E73;&#x5206;&#x6574;&#x4E2A;&#x6570;&#x7EC4;</strong></p>
<p>&#x200B;    <strong>&#x6B64;&#x65F6;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x516C;&#x5F0F;&#x5219;&#x4E3A;&#xFF1A;T[n] = 2T[n/2] + f(n)&#xFF1B;T[n/2]**</strong>&#x4E3A;&#x5E73;&#x5206;&#x540E;&#x7684;&#x5B50;&#x6570;&#x7EC4;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF0C;f[n] &#x4E3A;&#x5E73;&#x5206;&#x8FD9;&#x4E2A;&#x6570;&#x7EC4;&#x65F6;&#x6240;&#x82B1;&#x7684;&#x65F6;&#x95F4;&#xFF1B;</p>
<p>&#x6240;&#x4EE5;&#x6700;&#x597D;&#x60C5;&#x51B5;&#x4E0B;&#x662F;nlog(n)</p>
<p><strong>&#x6700;&#x5DEE;&#x60C5;&#x51B5;&#x4E0B;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</strong></p>
<p>&#x200B;    <strong>&#x6700;&#x5DEE;&#x7684;&#x60C5;&#x51B5;&#x5C31;&#x662F;&#x6BCF;&#x4E00;&#x6B21;&#x53D6;&#x5230;&#x7684;&#x5143;&#x7D20;&#x5C31;&#x662F;&#x6570;&#x7EC4;&#x4E2D;&#x6700;&#x5C0F;/&#x6700;&#x5927;&#x7684;&#xFF0C;&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#x5176;&#x5B9E;&#x5C31;&#x662F;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x4E86;(&#x6BCF;&#x4E00;&#x6B21;&#x90FD;&#x6392;&#x597D;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x7684;&#x987A;&#x5E8F;)</strong></p>
<p>   <strong>&#x8FD9;&#x79CD;&#x60C5;&#x51B5;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5C31;&#x597D;&#x8BA1;&#x7B97;&#x4E86;&#xFF0C;&#x5C31;&#x662F;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#xFF1A;T[n] = n * (n-1) = n^2 + n;</strong></p>
<p>   <strong><em>\</em>&#x7EFC;&#x4E0A;&#x6240;&#x8FF0;&#xFF1A;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x6700;&#x5DEE;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;&#xFF1A;O( n^2 )**</strong></p>
<h3 id="2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><a name="2&#x5F52;&#x5E76;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x5F52;&#x5E76;&#x6392;&#x5E8F;" class="plugin-anchor" href="#2&#x5F52;&#x5E76;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x5F52;&#x5E76;&#x6392;&#x5E8F;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130142158.gif" alt=""></p>
<p>&#x7B97;&#x6CD5;&#x601D;&#x60F3;:&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x662F;&#x5EFA;&#x7ACB;&#x5728;&#x5F52;&#x5E76;&#x64CD;&#x4F5C;&#x4E0A;&#x7684;&#x4E00;&#x79CD;&#x6709;&#x6548;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x8BE5;&#x7B97;&#x6CD5;&#x662F;&#x91C7;&#x7528;&#x5206;&#x6CBB;&#x6CD5;&#xFF08;Divide and Conquer&#xFF09;&#x7684;&#x4E00;&#x4E2A;&#x975E;&#x5E38;&#x5178;&#x578B;&#x7684;&#x5E94;&#x7528;&#x3002;&#x5C06;&#x5DF2;&#x6709;&#x5E8F;&#x7684;&#x5B50;&#x5E8F;&#x5217;&#x5408;&#x5E76;&#xFF0C;&#x5F97;&#x5230;&#x5B8C;&#x5168;&#x6709;&#x5E8F;&#x7684;&#x5E8F;&#x5217;&#xFF1B;&#x5373;&#x5148;&#x4F7F;&#x6BCF;&#x4E2A;&#x5B50;&#x5E8F;&#x5217;&#x6709;&#x5E8F;&#xFF0C;&#x518D;&#x4F7F;&#x5B50;&#x5E8F;&#x5217;&#x6BB5;&#x95F4;&#x6709;&#x5E8F;&#x3002;&#x82E5;&#x5C06;&#x4E24;&#x4E2A;&#x6709;&#x5E8F;&#x8868;&#x5408;&#x5E76;&#x6210;&#x4E00;&#x4E2A;&#x6709;&#x5E8F;&#x8868;&#xFF0C;&#x79F0;&#x4E3A;&#x4E8C;&#x8DEF;&#x5F52;&#x5E76;&#x3002;</p>
<p>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;: <a href="https://private.codecogs.com/gif.latex?O(n*logn" target="_blank"><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130142239.gif" alt="O(n*logn)"></a>) &#x3002;</p>
<pre><code class="lang-c++"><span class="hljs-comment">//&#x5F52;&#x5E76;&#x6392;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">merge</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr,<span class="hljs-keyword">int</span> start,<span class="hljs-keyword">int</span> mid,<span class="hljs-keyword">int</span> end)</span></span>{
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; tempArr(end-start+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>);
    <span class="hljs-keyword">int</span> left = start;
    <span class="hljs-keyword">int</span> right = mid+<span class="hljs-number">1</span>;
    <span class="hljs-keyword">int</span> index=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>( left&lt;=mid &amp;&amp; right&lt;=end){
        <span class="hljs-keyword">if</span>( arr[left] &lt;= arr[right] ){
            tempArr[index++]=arr[left++];
        }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(arr[left]&gt;=arr[right]){
            tempArr[index++]=arr[right++];
        }
    }
    <span class="hljs-keyword">while</span>(left&lt;=mid){
        tempArr[index++]=arr[left++];
    }
    <span class="hljs-keyword">while</span>(right&lt;=end){
        tempArr[index++]=arr[right++];
    }
    index=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">while</span>(start&lt;=end){
        arr[start++]=tempArr[index++];
    }
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">merge_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr,<span class="hljs-keyword">int</span> start,<span class="hljs-keyword">int</span> end)</span></span>{
    <span class="hljs-keyword">if</span>(start&lt;end){
        <span class="hljs-keyword">int</span> mid=start+(end-start)/<span class="hljs-number">2</span>;
        merge_sort(arr,start,mid);
        merge_sort(arr,mid+<span class="hljs-number">1</span>,end);
        merge(arr,start,mid, end);
    }
}
</code></pre>
<h3 id="3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><a name="3&#x9009;&#x62E9;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x9009;&#x62E9;&#x6392;&#x5E8F;" class="plugin-anchor" href="#3&#x9009;&#x62E9;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x9009;&#x62E9;&#x6392;&#x5E8F;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130142607.gif" alt=""></p>
<p>&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x662F;&#x4E00;&#x79CD;&#x7B80;&#x5355;&#x76F4;&#x89C2;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;&#x5B83;&#x7684;&#x5DE5;&#x4F5C;&#x539F;&#x7406;&#x662F;&#x6BCF;&#x4E00;&#x6B21;&#x4ECE;&#x5F85;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x636E;&#x5143;&#x7D20;&#x4E2D;&#x9009;&#x51FA;&#x6700;&#x5C0F;&#xFF08;&#x6216;&#x6700;&#x5927;&#xFF09;&#x7684;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x5B58;&#x653E;&#x5728;&#x5E8F;&#x5217;&#x7684;&#x8D77;&#x59CB;&#x4F4D;&#x7F6E;&#xFF0C;&#x76F4;&#x5230;&#x5168;&#x90E8;&#x5F85;&#x6392;&#x5E8F;&#x7684;&#x6570;&#x636E;&#x5143;&#x7D20;&#x6392;&#x5B8C;&#x3002; &#x9009;&#x62E9;&#x6392;&#x5E8F;&#x662F;&#x4E0D;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x65B9;&#x6CD5;&#x3002;</p>
<p>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;&#xFF1A; <a href="https://private.codecogs.com/gif.latex?O(n^{2}" target="_blank"><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130142552.gif" alt="O(n^{2})"></a>) </p>
<pre><code>void select_sort( vector&lt;int&gt;&amp; arr,int start,int end  ){
    int swap=0;
    for (int i = 0; i &lt;arr.size()-1 ; ++i) {
        int pos= i;
        for(int j=i+1;j&lt;arr.size();j++){
            if( arr[j]&lt;arr[pos] ){
                pos=j;
            }
        }
        swap = arr[pos];
        arr[pos] = arr[i];
        arr[i] = swap;
    }
}
</code></pre><h3 id="4&#x5806;&#x6392;&#x5E8F;"><a name="4&#x5806;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#4&#x5806;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x5806;&#x6392;&#x5E8F;" class="plugin-anchor" href="#4&#x5806;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x5806;&#x6392;&#x5E8F;</h3>
<p>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;&#xFF1A; <a href="https://private.codecogs.com/gif.latex?O(n*logn" target="_blank"><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130144437.gif" alt="O(n*logn)"></a>) </p>
<p><img src="https://img-blog.csdnimg.cn/20200413201908995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppc3V1,size_16,color_FFFFFF,t_70" alt="&#x5728;&#x8FD9;&#x91CC;&#x63D2;&#x5165;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<p><strong>&#x4E24;&#x4E2A;&#x7279;&#x6027;</strong></p>
<p>&#x7ED3;&#x6784;&#x6027;&#xFF1A;&#x7528;&#x6570;&#x7EC4;&#x8868;&#x793A;&#x7684;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;</p>
<p>&#x6709;&#x5E8F;&#x6027;&#xFF1A;&#x4EFB;&#x4E00;&#x7ED3;&#x70B9;&#x7684;&#x5173;&#x952E;&#x5B57;&#x662F;&#x5176;&#x5B50;&#x6811;&#x6240;&#x6709;&#x7ED3;&#x70B9;&#x7684;&#x6700;&#x5927;&#x503C;&#xFF08;&#x6216;&#x6700;&#x5C0F;&#x503C;&#xFF09;</p>
<pre><code>&#x201C;&#x6700;&#x5927;&#x5806;(MaxHeap)&#x201D;&#xFF0C;&#x4E5F;&#x79F0;&quot;&#x5927;&#x9876;&#x5806;&quot;&#xFF1A;&#x6700;&#x5927;&#x503C;
</code></pre><p><img src="https://img-blog.csdnimg.cn/20200413202008385.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppc3V1,size_16,color_FFFFFF,t_70" alt="&#x5728;&#x8FD9;&#x91CC;&#x63D2;&#x5165;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<pre><code>&#x6700;&#x5C0F;&#x5806;(MinHeap)&#x201D;&#xFF0C;&#x4E5F;&#x79F0;&quot;&#x5C0F;&#x9876;&#x5806;&quot;&#xFF1A;&#x6700;&#x5C0F;&#x503C;
</code></pre><p><img src="https://img-blog.csdnimg.cn/20200413202025159.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ppc3V1,size_16,color_FFFFFF,t_70" alt="&#x5728;&#x8FD9;&#x91CC;&#x63D2;&#x5165;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<h4 id="&#x6784;&#x5EFA;&#x6700;&#x5927;&#x5806;"><a name="&#x6784;&#x5EFA;&#x6700;&#x5927;&#x5806;" class="anchor-navigation-ex-anchor" href="#&#x6784;&#x5EFA;&#x6700;&#x5927;&#x5806;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x6784;&#x5EFA;&#x6700;&#x5927;&#x5806;" class="plugin-anchor" href="#&#x6784;&#x5EFA;&#x6700;&#x5927;&#x5806;"><i class="fa fa-link" aria-hidden="true"></i></a><strong>&#x6784;&#x5EFA;&#x6700;&#x5927;&#x5806;</strong></h4>
<p><strong>&#x5EFA;&#x7ACB;&#x5806;&#x7684;&#x4E3B;&#x8981;&#x51FD;&#x6570;</strong>
&#x5B58;&#x50A8;&#x7ED3;&#x6784;&#x4F53;:</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">struct</span> node{
    <span class="hljs-keyword">int</span> *data;
    <span class="hljs-keyword">int</span> size;
};
</code></pre>
<p><strong>1 create() &#x521D;&#x59CB;&#x5316;&#x5806;</strong></p>
<pre><code class="lang-cpp"><span class="hljs-keyword">typedef</span> node *tree;
<span class="hljs-function">tree <span class="hljs-title">create</span><span class="hljs-params">(<span class="hljs-keyword">int</span> size)</span></span>{
    tree t=<span class="hljs-keyword">new</span> node;
    t-&gt;size=<span class="hljs-number">0</span>;
    t-&gt;data=(<span class="hljs-keyword">int</span> *)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">int</span>)*(size+<span class="hljs-number">10</span>));
    t-&gt;data[<span class="hljs-number">0</span>]=<span class="hljs-number">-1000000</span>;<span class="hljs-comment">//&#x8BBE;&#x7F6E;&#x54E8;&#x5175;&#x503C;</span>
    <span class="hljs-keyword">return</span> t;
}
</code></pre>
<p>&#x8FD9;&#x91CC;&#x4E3A;&#x4EC0;&#x4E48;&#x8981;&#x8BBE;&#x7F6E;&#x54E8;&#x5175;&#x503C;&#x5462;?&#x5728;&#x4E0B;&#x9762;&#x5206;&#x6790;
<strong>2 insert() &#x63D2;&#x5165;&#x503C;</strong>
&#x4E3B;&#x8981;&#x601D;&#x8DEF;:&#x5F80;&#x6570;&#x7EC4;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;+1&#x63D2;&#x5165;&#x503C;,&#x7136;&#x540E;&#x548C;&#x524D;&#x9762;&#x7684;&#x7236;&#x8282;&#x70B9;(&#x56E0;&#x4E3A;&#x662F;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#x53C8;&#x662F;&#x6570;&#x7EC4;&#x5B58;&#x50A8;,&#x5176;&#x7236;&#x8282;&#x70B9;&#x53EF;&#x4EE5;&#x76F4;&#x63A5;&#x7528;i/2&#x8868;&#x793A;)&#x6BD4;&#x8F83;,&#x5982;&#x679C;&#x6BD4;&#x7236;&#x8282;&#x70B9;&#x5927;&#x5C31;&#x548C;&#x7236;&#x8282;&#x70B9;&#x66FF;&#x6362;&#x4F4D;&#x7F6E;</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">insert</span><span class="hljs-params">(tree t,<span class="hljs-keyword">int</span> item)</span></span>{
    <span class="hljs-keyword">int</span> i=++t-&gt;size;<span class="hljs-comment">//&#x83B7;&#x53D6;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;+1;</span>
    <span class="hljs-keyword">for</span>(;t-&gt;data[i/<span class="hljs-number">2</span>]&lt;item;i/=<span class="hljs-number">2</span>){<span class="hljs-comment">//&#x548C;&#x524D;&#x9762;&#x7684;&#x7236;&#x8282;&#x70B9;&#x6BD4;&#x8F83;,</span>
    <span class="hljs-comment">//&#x5982;&#x679C;&#x5728;&#x4E0A;&#x9762;&#x6CA1;&#x6709;&#x8BBE;&#x7F6E;&#x54E8;&#x5175;&#x503C;,&#x4F1A;&#x5BFC;&#x81F4;&#x5982;&#x679C;&#x63D2;&#x5165;&#x7684;&#x8282;&#x70B9;&#x6BD4;&#x7B2C;&#x4E00;&#x4E2A;&#x6839;&#x8282;&#x70B9;&#x8FD8;&#x5927;,&#x90A3;&#x4E48;&#x8BE5;&#x5FAA;&#x73AF;&#x4E0D;&#x4F1A;&#x7ED3;&#x675F;,&#x4F1A;&#x56E0;&#x4E3A;&#x4E00;&#x76F4;&#x548C;data[0]&#x6BD4;&#x8F83;&#x800C;&#x65E0;&#x9650;&#x7684;&#x5FAA;&#x73AF;&#x4E0B;&#x53BB;</span>
        t-&gt;data[i]=t-&gt;data[i/<span class="hljs-number">2</span>];
    }
    t-&gt;data[i]=item;<span class="hljs-comment">//&#x6700;&#x540E;&#x5728;&#x8BE5;&#x4F4D;&#x7F6E;&#x63D2;&#x5165;&#x503C;</span>
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
}
</code></pre>
<p><strong>3delete() &#x5220;&#x9664;&#x6839;&#x8282;&#x70B9;</strong>
&#x601D;&#x8DEF;:&#x8981;&#x5220;&#x7684;&#x80AF;&#x5B9A;&#x662F;&#x6839;&#x8282;&#x70B9;(&#x6700;&#x5927;&#x5806;&#x5C31;&#x662F;&#x5220;&#x9664;&#x4E00;&#x4E2A;&#x6700;&#x5927;&#x503C;),&#x63A5;&#x7740;&#x53D6;&#x51FA;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;,&#x653E;&#x5728;&#x7B2C;&#x4E00;&#x4F4D;,&#x7136;&#x540E;&#x4ECE;&#x7B2C;&#x4E00;&#x4F4D;&#x5F00;&#x59CB;&#x5F80;&#x540E;&#x6BD4;&#x8F83;,&#x6BD4;&#x540E;&#x9762;&#x5C0F;,&#x5C31;&#x548C;&#x540E;&#x9762;&#x7684;&#x5B50;&#x8282;&#x70B9;&#x66FF;&#x6362;&#x4F4D;&#x7F6E;,&#x540C;&#x7406;,&#x5B50;&#x8282;&#x70B9;&#x7528;i<em>2&#x6216;&#x8005;i</em>2+1&#x8868;&#x793A;,&#x6240;&#x4EE5;&#x5224;&#x65AD;&#x7684;&#x65F6;&#x5019;&#x9700;&#x8981;&#x5148;&#x6BD4;&#x8F83;&#x5B50;&#x8282;&#x70B9;&#x54EA;&#x4E2A;&#x6BD4;&#x8F83;&#x5927;
&#x8FD9;&#x91CC;&#x8981;&#x6CE8;&#x610F;&#x7684;&#x662F;,if(child!=h-&gt;size)&#x4EE3;&#x8868;&#x5F53;&#x524D;&#x7684;&#x8282;&#x70B9;&#x662F;&#x5426;&#x8FD8;&#x5B58;&#x5728;&#x5DE6;&#x53F3;&#x5B50;&#x8282;&#x70B9;,&#x5982;&#x679C;child==h-&gt;size,&#x8BF4;&#x660E;&#x5DF2;&#x7ECF;&#x5230;&#x4E86;&#x8FB9;&#x754C;,&#x90A3;&#x5C31;&#x6CA1;&#x6709;&#x5DE6;&#x53F3;&#x5B50;&#x8282;&#x70B9;&#x4E86;</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">Delete</span><span class="hljs-params">(tree h)</span></span>{
    <span class="hljs-keyword">if</span>(h-&gt;size==<span class="hljs-number">0</span>){
        <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x5DF2;&#x7ECF;&#x6CA1;&#x6709;&#x5143;&#x7D20;&#x4E86;&quot;</span>;
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>; 
    }
    <span class="hljs-keyword">int</span> parent,child;
    <span class="hljs-keyword">int</span> maxData=h-&gt;data[<span class="hljs-number">1</span>];
    <span class="hljs-keyword">int</span> top=h-&gt;data[h-&gt;size--];<span class="hljs-comment">//&#x53BB;&#x9664;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;,&#x653E;&#x5728;&#x6839;&#x8282;&#x70B9;,</span>
    <span class="hljs-comment">//&#x4E0B;&#x9762;&#x8FD9;&#x4E2A;&#x5FAA;&#x73AF;&#x7528;&#x6765;&#x5BFB;&#x627E;&#x653E;&#x7F6E;top&#x7684;&#x4F4D;&#x7F6E; </span>
    <span class="hljs-keyword">for</span>(parent=<span class="hljs-number">1</span>;parent*<span class="hljs-number">2</span>&lt;=h-&gt;size;parent=child){
        child=parent*<span class="hljs-number">2</span>;
        <span class="hljs-keyword">if</span>(child!=h-&gt;size){<span class="hljs-comment">//&#x5982;&#x679C;&#x5B58;&#x5728;&#x5DE6;&#x53F3;&#x513F;&#x5B50;&#x7684;&#x60C5;&#x51B5; </span>
            <span class="hljs-keyword">if</span>(h-&gt;data[child]&lt;h-&gt;data[child+<span class="hljs-number">1</span>])child++;<span class="hljs-comment">//&#x627E;&#x51FA;&#x5DE6;&#x53F3;&#x513F;&#x5B50;&#x7684;&#x8F83;&#x5927;&#x8005; </span>
        }
        <span class="hljs-keyword">if</span>(top&gt;=h-&gt;data[child])<span class="hljs-keyword">break</span>;<span class="hljs-comment">//&#x627E;&#x5230;&#x4E86;</span>
        <span class="hljs-comment">//&#x5426;&#x5219;&#x8BA9;&#x5DE6;&#x53F3;&#x513F;&#x5B50;&#x8F83;&#x5927;&#x7684;&#x66FF;&#x6362;&#x5F53;&#x524D;parent&#x8282;&#x70B9;</span>
        <span class="hljs-keyword">else</span> 
           h-&gt;data[parent]=h-&gt;data[child]; 
    }
    <span class="hljs-comment">//&#x6700;&#x540E;&#x653E;&#x5165;</span>
    h-&gt;data[parent]=top;
    <span class="hljs-keyword">return</span> maxData;
}
</code></pre>
<h4 id="&#x6784;&#x5EFA;&#x5806;&#x7684;&#x8C03;&#x6574;"><a name="&#x6784;&#x5EFA;&#x5806;&#x7684;&#x8C03;&#x6574;" class="anchor-navigation-ex-anchor" href="#&#x6784;&#x5EFA;&#x5806;&#x7684;&#x8C03;&#x6574;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x6784;&#x5EFA;&#x5806;&#x7684;&#x8C03;&#x6574;" class="plugin-anchor" href="#&#x6784;&#x5EFA;&#x5806;&#x7684;&#x8C03;&#x6574;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x6784;&#x5EFA;&#x5806;&#x7684;&#x8C03;&#x6574;</h4>
<p>&#x5C06; N &#x4E2A;&#x5143;&#x7D20;&#x76F4;&#x63A5;&#x6309;&#x987A;&#x5E8F;&#x5B58;&#x5165;&#xFF0C;&#x518D;&#x8C03;&#x6574;&#x5404;&#x7ED3;&#x70B9;&#x7684;&#x4F4D;&#x7F6E;&#xFF08;&#x7B80;&#x5355;&#x8BF4;&#x6765;&#xFF0C;&#x5BF9;&#x4E8E;&#x4ECE;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x6709;&#x5B69;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x7ED3;&#x70B9;&#x6765;&#x8BF4;&#xFF0C;&#x5176;&#x672C;&#x8EAB;&#x7ED3;&#x70B9;&#x548C;&#x5B69;&#x5B50;&#x7ED3;&#x70B9;&#x5171;&#x540C;&#x6784;&#x6210;&quot;&#x5B50;&#x6700;&#x5C0F;&#x5806;&quot;&#xFF0C;&#x501F;&#x52A9;&#x524D;&#x9762;&#x5220;&#x9664;&#x7684;&#x60F3;&#x6CD5;&#xFF0C;&#x5BF9;&#x6BCF;&#x4E2A;&quot;&#x5B50;&#x6700;&#x5C0F;&#x5806;&quot;&#x6392;&#x5E8F;&#xFF0C;&#x5F53;&#x6392;&#x5E8F;&#x5B8C;&#x6210;&#xFF0C;&#x6574;&#x4E2A;&#x6700;&#x5C0F;&#x5806;&#x4E5F;&#x5EFA;&#x7ACB;&#x6210;&#x529F;&#xFF09;</p>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> maxdata 100000</span>
<span class="hljs-keyword">struct</span> node{
    <span class="hljs-keyword">int</span> * data;
    <span class="hljs-keyword">int</span> size;
    <span class="hljs-keyword">int</span> capacity;
};
<span class="hljs-keyword">typedef</span> node * tree;
<span class="hljs-function">tree <span class="hljs-title">create</span><span class="hljs-params">(<span class="hljs-keyword">int</span> maxsize)</span></span>{
    tree h=<span class="hljs-keyword">new</span> node;
    h-&gt;data=(<span class="hljs-keyword">int</span> *)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">int</span>)*(maxsize+<span class="hljs-number">1</span>));
    h-&gt;size=<span class="hljs-number">0</span>;
    h-&gt;capacity=maxsize;
    h-&gt;data[<span class="hljs-number">0</span>]=maxdata;
    <span class="hljs-keyword">return</span> h;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">LevelOrderTraversal</span><span class="hljs-params">(tree H)</span></span>{
    <span class="hljs-keyword">int</span> i;
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;&#x5C42;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x662F;&#xFF1A;&quot;</span>);
    <span class="hljs-keyword">for</span>(i = <span class="hljs-number">1</span>;i&lt;=H-&gt;size;i++){
        <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;%d &quot;</span>,H-&gt;data[i]);
    } 
    <span class="hljs-built_in">printf</span>(<span class="hljs-string">&quot;\n&quot;</span>); 
} 
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Heapify</span><span class="hljs-params">(tree h,<span class="hljs-keyword">int</span> i)</span></span>{
    <span class="hljs-keyword">int</span> parent,child;
    <span class="hljs-keyword">int</span> data=h-&gt;data[i];
    <span class="hljs-keyword">for</span>(parent=i;parent*<span class="hljs-number">2</span>&lt;=h-&gt;size;parent=child){
        child=parent*<span class="hljs-number">2</span>;
        <span class="hljs-keyword">if</span>(child!=h-&gt;size){
            <span class="hljs-keyword">if</span>(h-&gt;data[child]&lt;h-&gt;data[child+<span class="hljs-number">1</span>])child++;
        }
        <span class="hljs-keyword">if</span>(h-&gt;data[child]&lt;=data)<span class="hljs-keyword">break</span>;
        <span class="hljs-keyword">else</span> h-&gt;data[parent]=h-&gt;data[child];
    }
    h-&gt;data[parent]=data;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">adjust</span><span class="hljs-params">(tree h)</span></span>{
    <span class="hljs-keyword">int</span> i=h-&gt;size/<span class="hljs-number">2</span>;
    <span class="hljs-keyword">for</span>(;i&gt;<span class="hljs-number">0</span>;i--){
        Heapify(h,i);<span class="hljs-comment">//&#x4ECE;&#x6700;&#x62E5;&#x6709;&#x5B50;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x6811;&#x5F00;&#x59CB;--&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x7279;&#x6027;,&#x53EF;&#x4EE5;&#x81EA;&#x5DF1;&#x753B;&#x4E2A;&#x56FE;&#x9A8C;&#x8BC1;&#x4E00;&#x4E0B;</span>
    } 
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    tree h;
    h=create(<span class="hljs-number">100</span>);
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">cin</span>&gt;&gt;n;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-built_in">cin</span>&gt;&gt;h-&gt;data[++h-&gt;size];
    }
    adjust(h);
    LevelOrderTraversal(h);
}
</code></pre>
<h3 id="5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><a name="5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;" class="plugin-anchor" href="#5&#x5E0C;&#x5C14;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>5.&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</h3>
<p>&#x5728;&#x6700;&#x574F;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;: O(n^2)
&#x6700;&#x597D;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;&#xFF1A; O(n)
&#x5E73;&#x5747;&#x60C5;&#x51B5;&#x4E0B;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;&#xFF1A;O(n^1.3)</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130145020.gif" alt="C#&#x7B97;&#x6CD5;&#x8BBE;&#x8BA1;&#x6392;&#x5E8F;&#x7BC7;&#x4E4B;07-&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#xFF08;&#x9644;&#x5E26;&#x52A8;&#x753B;&#x6F14;&#x793A;&#x7A0B;&#x5E8F;&#xFF09;"></p>
<p>&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x7684;&#x5B9E;&#x8D28;&#x5C31;&#x662F;&#x5206;&#x7EC4;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF0C;&#x8BE5;&#x65B9;&#x6CD5;&#x53C8;&#x79F0;&#x7F29;&#x5C0F;&#x589E;&#x91CF;&#x6392;&#x5E8F;</p>
<p>&#x8BE5;&#x65B9;&#x6CD5;&#x7684;&#x57FA;&#x672C;&#x601D;&#x60F3;&#x662F;&#xFF1A;&#x5148;&#x5C06;&#x6574;&#x4E2A;&#x5F85;&#x6392;&#x5143;&#x7D20;&#x5E8F;&#x5217;&#x5206;&#x5272;&#x6210;&#x82E5;&#x5E72;&#x4E2A;&#x5B50;&#x5E8F;&#x5217;&#xFF08;&#x7531;&#x76F8;&#x9694;&#x67D0;&#x4E2A;&#x201C;&#x589E;&#x91CF;&#x201D;&#x7684;&#x5143;&#x7D20;&#x7EC4;&#x6210;&#x7684;&#xFF09;&#x5206;&#x522B;&#x8FDB;&#x884C;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF0C;&#x7136;&#x540E;&#x4F9D;&#x6B21;&#x7F29;&#x51CF;&#x589E;&#x91CF;&#x518D;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#xFF0C;&#x5F85;&#x6574;&#x4E2A;&#x5E8F;&#x5217;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x57FA;&#x672C;&#x6709;&#x5E8F;&#xFF08;&#x589E;&#x91CF;&#x8DB3;&#x591F;&#x5C0F;&#xFF09;&#x65F6;&#xFF0C;&#x518D;&#x5BF9;&#x5168;&#x4F53;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x4E00;&#x6B21;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x3002;&#x56E0;&#x4E3A;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x5728;&#x5143;&#x7D20;&#x57FA;&#x672C;&#x6709;&#x5E8F;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#xFF08;&#x63A5;&#x8FD1;&#x6700;&#x597D;&#x60C5;&#x51B5;&#xFF09;&#xFF0C;&#x6548;&#x7387;&#x662F;&#x5F88;&#x9AD8;&#x7684;&#xFF0C;&#x56E0;&#x6B64;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x5728;&#x65F6;&#x95F4;&#x6548;&#x7387;&#x4E0A;&#x6BD4;&#x524D;&#x4E24;&#x79CD;&#x65B9;&#x6CD5;&#x6709;&#x8F83;&#x5927;&#x63D0;&#x9AD8;&#x3002;</p>
<p>&#x4EE5;n=10&#x7684;&#x4E00;&#x4E2A;&#x6570;&#x7EC4;49, 38, 65, 97, 26, 13, 27, 49, 55, 4&#x4E3A;&#x4F8B;</p>
<p><strong>&#x7B2C;&#x4E00;&#x6B21; gap = 10 / 2 = 5</strong></p>
<p>49   38   65   97   26   13   27   49   55   4</p>
<p>1A                                        1B</p>
<p>&#x200B;        2A                                         2B</p>
<p>&#x200B;                 3A                                         3B</p>
<p>&#x200B;                         4A                                          4B</p>
<p>&#x200B;                                  5A                                         5B</p>
<p><em>1A,1B&#xFF0C;2A,2B&#x7B49;&#x4E3A;&#x5206;&#x7EC4;&#x6807;&#x8BB0;&#xFF0C;&#x6570;&#x5B57;&#x76F8;&#x540C;&#x7684;&#x8868;&#x793A;&#x5728;&#x540C;&#x4E00;&#x7EC4;&#xFF0C;&#x5927;&#x5199;&#x5B57;&#x6BCD;&#x8868;&#x793A;&#x662F;&#x8BE5;&#x7EC4;&#x7684;&#x7B2C;&#x51E0;&#x4E2A;&#x5143;&#x7D20;&#xFF0C; &#x6BCF;&#x6B21;&#x5BF9;&#x540C;&#x4E00;&#x7EC4;&#x7684;&#x6570;&#x636E;&#x8FDB;&#x884C;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x3002;&#x5373;&#x5206;&#x6210;&#x4E86;&#x4E94;&#x7EC4;(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)&#x8FD9;&#x6837;&#x6BCF;&#x7EC4;&#x6392;&#x5E8F;&#x540E;&#x5C31;&#x53D8;&#x6210;&#x4E86;(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26)&#xFF0C;&#x4E0B;&#x540C;&#x3002;</em></p>
<p><strong>&#x7B2C;&#x4E8C;&#x6B21; gap = 5 / 2 = 2</strong></p>
<p>&#x6392;&#x5E8F;&#x540E;</p>
<p>13   27   49   55   4    49   38   65   97   26</p>
<p>1A             1B             1C              1D            1E</p>
<p>&#x200B;        2A               2B             2C             2D              2E</p>
<p><strong>&#x7B2C;&#x4E09;&#x6B21; gap = 2 / 2 = 1</strong></p>
<p>4   26   13   27   38    49   49   55   97   65</p>
<p>1A   1B     1C    1D    1E      1F     1G    1H     1I     1J</p>
<p><strong>&#x7B2C;&#x56DB;&#x6B21; gap = 1 / 2 = 0 &#x6392;&#x5E8F;&#x5B8C;&#x6210;&#x5F97;&#x5230;&#x6570;&#x7EC4;&#xFF1A;</strong></p>
<p>4   13   26   27   38    49   49   55   65   97</p>
<p>&#x4E0B;&#x9762;&#x7ED9;&#x51FA;&#x4E25;&#x683C;&#x6309;&#x7167;&#x5B9A;&#x4E49;&#x6765;&#x5199;&#x7684;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</p>
<pre><code class="lang-c++"><span class="hljs-comment">//4.&#x5E0C;&#x5C14;&#x6392;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">shell_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; arr , <span class="hljs-keyword">int</span> n)</span></span>{
    <span class="hljs-keyword">for</span>( <span class="hljs-keyword">int</span> gap=n/<span class="hljs-number">2</span>; gap&gt;<span class="hljs-number">0</span> ;gap/=<span class="hljs-number">2</span>){
        <span class="hljs-keyword">for</span>( <span class="hljs-keyword">int</span> i=gap ;i&lt;arr.size();i+=gap){
            <span class="hljs-keyword">int</span> j=i;
            <span class="hljs-keyword">int</span> sentinel= arr[i];
            <span class="hljs-keyword">if</span>( arr[j]&lt;arr[j-gap] ){
                <span class="hljs-keyword">while</span>( j-gap&gt;=<span class="hljs-number">0</span> &amp;&amp; arr[j-gap] &gt; sentinel ){
                    arr[j]= arr[j-gap];
                    j-=gap;
                }
                arr[j]= sentinel;
            }
        }
    }
}
</code></pre>
<h3 id="6&#x8BA1;&#x6570;&#x6392;&#x5E8F;"><a name="6&#x8BA1;&#x6570;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#6&#x8BA1;&#x6570;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="6&#x8BA1;&#x6570;&#x6392;&#x5E8F;" class="plugin-anchor" href="#6&#x8BA1;&#x6570;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>6.&#x8BA1;&#x6570;&#x6392;&#x5E8F;</h3>
<p>&#x6709;&#x8FD9;&#x6837;&#x4E00;&#x9053;&#x6392;&#x5E8F;&#x9898;&#xFF1A;&#x6570;&#x7EC4;&#x91CC;&#x6709;20&#x4E2A;&#x968F;&#x673A;&#x6570;&#xFF0C;&#x53D6;&#x503C;&#x8303;&#x56F4;&#x4E3A;&#x4ECE;0&#x5230;10&#xFF0C;&#x8981;&#x6C42;&#x7528;&#x6700;&#x5FEB;&#x7684;&#x901F;&#x5EA6;&#x628A;&#x8FD9;20&#x4E2A;&#x6574;&#x6570;&#x4ECE;&#x5C0F;&#x5230;&#x5927;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;</p>
<p>&#x7B2C;&#x4E00;&#x65F6;&#x95F4;&#x4F60;&#x53EF;&#x80FD;&#x4F1A;&#x60F3;&#x4F7F;&#x7528;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#xFF0C;&#x56E0;&#x4E3A;&#x5FEB;&#x6392;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x53EA;&#x6709;O(nlogn)&#x3002;&#x4F46;&#x662F;&#x8FD9;&#x79CD;&#x65B9;&#x6CD5;&#x8FD8;&#x662F;&#x4E0D;&#x591F;&#x5FEB;&#xFF0C;&#x6709;&#x6CA1;&#x6709;&#x6BD4;O(nlogn)&#x66F4;&#x5FEB;&#x7684;&#x6392;&#x5E8F;&#x65B9;&#x6CD5;&#x5462;&#xFF1F;&#x4F60;&#x53EF;&#x80FD;&#x4F1A;&#x6709;&#x7591;&#x95EE;&#xFF1A;O(nlogn)&#x5DF2;&#x7ECF;&#x662F;&#x6700;&#x5FEB;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x4E86;&#xFF0C;&#x600E;&#x4E48;&#x53EF;&#x80FD;&#x8FD8;&#x6709;&#x66F4;&#x5FEB;&#x7684;&#x6392;&#x5E8F;&#x65B9;&#x6CD5;&#xFF1F;</p>
<p>&#x8BA9;&#x6211;&#x4EEC;&#x5148;&#x6765;&#x56DE;&#x987E;&#x4E00;&#x4E0B;&#x7ECF;&#x5178;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x65E0;&#x8BBA;&#x662F;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#xFF0C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x8FD8;&#x662F;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x7B49;&#x7B49;&#xFF0C;&#x90FD;&#x662F;&#x57FA;&#x4E8E;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x6BD4;&#x8F83;&#x6765;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x7684;&#x3002;&#x4F46;&#x662F;&#x6709;&#x4E00;&#x79CD;&#x7279;&#x6B8A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x53EB;<strong>&#x8BA1;&#x6570;&#x6392;&#x5E8F;</strong>&#xFF0C;&#x8FD9;&#x79CD;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x4E0D;&#x662F;&#x57FA;&#x4E8E;&#x5143;&#x7D20;&#x6BD4;&#x8F83;&#xFF0C;&#x800C;&#x662F;&#x5229;&#x7528;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#x6765;&#x786E;&#x5B9A;&#x5143;&#x7D20;&#x7684;&#x6B63;&#x786E;&#x4F4D;&#x7F6E;&#x3002;</p>
<p>&#x5728;&#x521A;&#x624D;&#x7684;&#x9898;&#x76EE;&#x91CC;&#xFF0C;&#x968F;&#x5373;&#x6574;&#x6570;&#x7684;&#x53D6;&#x503C;&#x8303;&#x56F4;&#x662F;&#x4ECE;0&#x5230;10&#xFF0C;&#x90A3;&#x4E48;&#x8FD9;&#x4E9B;&#x6574;&#x6570;&#x7684;&#x503C;&#x80AF;&#x5B9A;&#x662F;&#x5728;0&#x5230;10&#x8FD9;11&#x4E2A;&#x6570;&#x91CC;&#x9762;&#x3002;&#x4E8E;&#x662F;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5EFA;&#x7ACB;&#x4E00;&#x4E2A;&#x957F;&#x5EA6;&#x4E3A;11&#x7684;&#x6570;&#x7EC4;&#xFF0C;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#x4ECE;0&#x5230;10&#xFF0C;&#x5143;&#x7D20;&#x521D;&#x59CB;&#x503C;&#x5168;&#x4E3A;0&#xFF0C;&#x5982;&#x4E0B;&#x6240;&#x793A;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130163414.png" alt="image-20201130163414905"></p>
<p>&#x5148;&#x5047;&#x8BBE;20&#x4E2A;&#x968F;&#x673A;&#x6574;&#x6570;&#x7684;&#x503C;&#x662F;&#xFF1A;<strong>9, 3, 5, 4, 9, 1, 2, 7, 8&#xFF0C;1&#xFF0C;3, 6, 5, 3, 4, 0, 10, 9, 7, 9</strong></p>
<p>&#x8BA9;&#x6211;&#x4EEC;&#x5148;&#x904D;&#x5386;&#x8FD9;&#x4E2A;&#x65E0;&#x5E8F;&#x7684;&#x968F;&#x673A;&#x6570;&#x7EC4;&#xFF0C;&#x6BCF;&#x4E00;&#x4E2A;&#x6574;&#x6570;&#x6309;&#x7167;&#x5176;&#x503C;&#x5BF9;&#x53F7;&#x5165;&#x5EA7;&#xFF0C;&#x5BF9;&#x5E94;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#x7684;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x52A0;1&#x64CD;&#x4F5C;&#x3002;</p>
<p>&#x6BD4;&#x5982;&#x7B2C;&#x4E00;&#x4E2A;&#x6574;&#x6570;&#x662F;9&#xFF0C;&#x90A3;&#x4E48;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#x4E3A;9&#x7684;&#x5143;&#x7D20;&#x52A0;1&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130163421.png" alt="image-20201130163421937"></p>
<p>&#x7B2C;&#x4E8C;&#x4E2A;&#x6574;&#x6570;&#x662F;3&#xFF0C;&#x90A3;&#x4E48;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#x4E3A;3&#x7684;&#x5143;&#x7D20;&#x52A0;1&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130163428.png" alt="image-20201130163428894"></p>
<p>&#x7EE7;&#x7EED;&#x904D;&#x5386;&#x6570;&#x5217;&#x5E76;&#x4FEE;&#x6539;&#x6570;&#x7EC4;......</p>
<p>&#x6700;&#x7EC8;&#xFF0C;&#x6570;&#x5217;&#x904D;&#x5386;&#x5B8C;&#x6BD5;&#x65F6;&#xFF0C;&#x6570;&#x7EC4;&#x7684;&#x72B6;&#x6001;&#x5982;&#x4E0B;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130163436.png" alt="image-20201130163436701"></p>
<p>&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x6BCF;&#x4E00;&#x4E2A;&#x503C;&#xFF0C;&#x4EE3;&#x8868;&#x4E86;&#x6570;&#x5217;&#x4E2D;&#x5BF9;&#x5E94;&#x6574;&#x6570;&#x7684;&#x51FA;&#x73B0;&#x6B21;&#x6570;&#x3002;</p>
<p>&#x6709;&#x4E86;&#x8FD9;&#x4E2A;&#x7EDF;&#x8BA1;&#x7ED3;&#x679C;&#xFF0C;&#x6392;&#x5E8F;&#x5C31;&#x5F88;&#x7B80;&#x5355;&#x4E86;&#xFF0C;&#x76F4;&#x63A5;&#x904D;&#x5386;&#x6570;&#x7EC4;&#xFF0C;&#x8F93;&#x51FA;&#x6570;&#x7EC4;&#x5143;&#x7D20;&#x7684;&#x4E0B;&#x6807;&#x503C;&#xFF0C;&#x5143;&#x7D20;&#x7684;&#x503C;&#x662F;&#x51E0;&#xFF0C;&#x5C31;&#x8F93;&#x51FA;&#x51E0;&#x6B21;&#xFF1A;</p>
<p><strong>0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10</strong></p>
<p>&#x663E;&#x7136;&#xFF0C;&#x8FD9;&#x4E2A;&#x8F93;&#x51FA;&#x7684;&#x6570;&#x5217;&#x5DF2;&#x7ECF;&#x662F;&#x6709;&#x5E8F;&#x7684;&#x4E86;&#x3002;</p>
<p>&#x8FD9;&#x5C31;&#x662F;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x57FA;&#x672C;&#x8FC7;&#x7A0B;&#xFF0C;&#x5B83;<strong>&#x9002;&#x7528;&#x4E8E;&#x4E00;&#x5B9A;&#x8303;&#x56F4;&#x7684;&#x6574;&#x6570;&#x6392;&#x5E8F;</strong>&#x3002;<strong>&#x5728;&#x53D6;&#x503C;&#x8303;&#x56F4;&#x4E0D;&#x662F;&#x5F88;&#x5927;&#x7684;&#x60C5;&#x51B5;&#x4E0B;&#xFF0C;&#x5B83;&#x7684;&#x6027;&#x80FD;&#x5728;&#x67D0;&#x4E9B;&#x60C5;&#x51B5;&#x751A;&#x81F3;&#x5FEB;&#x8FC7;&#x90A3;&#x4E9B;O(nlogn)&#x7684;&#x6392;&#x5E8F;&#xFF0C;&#x4F8B;&#x5982;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x3001;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x3002;</strong></p>
<p>&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x662F;O(n+k)</p>
<p>&#x4EE3;&#x7801;&#x5B9E;&#x73B0;&#x5982;&#x4E0B;&#xFF1A;</p>
<pre><code class="lang-c++"><span class="hljs-comment">//5.&#x8BA1;&#x6570;&#x6392;&#x5E8F;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">counting_sort</span><span class="hljs-params">( <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; &amp; arr ,<span class="hljs-keyword">int</span> n)</span></span>{
    <span class="hljs-keyword">int</span> minE = arr[<span class="hljs-number">0</span>];
    <span class="hljs-keyword">int</span> maxE = minE;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> k:arr){
        <span class="hljs-keyword">if</span>(k &gt; maxE)maxE=k;
        <span class="hljs-keyword">if</span>(k &lt; minE)minE=k;
    }
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; counting(maxE - minE + <span class="hljs-number">1</span>, <span class="hljs-number">0</span>);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> k:arr){
        counting[k - minE]+=<span class="hljs-number">1</span>;
    }
    <span class="hljs-keyword">int</span> index=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;counting.size();i++){
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;counting[i];j++){
            arr[index++]= i + minE;
        }
    }
}
</code></pre>
<h3 id="7&#x57FA;&#x6570;&#x6392;&#x5E8F;"><a name="7&#x57FA;&#x6570;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#7&#x57FA;&#x6570;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="7&#x57FA;&#x6570;&#x6392;&#x5E8F;" class="plugin-anchor" href="#7&#x57FA;&#x6570;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>7.&#x57FA;&#x6570;&#x6392;&#x5E8F;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130172130.gif" alt="C#&#x7B97;&#x6CD5;&#x8BBE;&#x8BA1;&#x6392;&#x5E8F;&#x7BC7;&#x4E4B;09-&#x57FA;&#x6570;&#x6392;&#x5E8F;&#xFF08;&#x9644;&#x5E26;&#x52A8;&#x753B;&#x6F14;&#x793A;&#x7A0B;&#x5E8F;&#xFF09;"></p>
<p>&#x3000;&#x901A;&#x8FC7;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x5BF9;&#x6570;&#x7EC4;{53, 3, 542, 748, 14, 214, 154, 63, 616}&#xFF0C;&#x5B83;&#x7684;&#x793A;&#x610F;&#x56FE;&#x5982;&#x4E0B;&#xFF1A;</p>
<p><a href="https://images0.cnblogs.com/i/497634/201403/161837176365265.jpg" target="_blank"><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130172500.jpeg" alt="img"></a></p>
<p>&#x5728;&#x4E0A;&#x56FE;&#x4E2D;&#xFF0C;&#x9996;&#x5148;&#x5C06;&#x6240;&#x6709;&#x5F85;&#x6BD4;&#x8F83;&#x6811;&#x8102;&#x7EDF;&#x4E00;&#x4E3A;&#x7EDF;&#x4E00;&#x4F4D;&#x6570;&#x957F;&#x5EA6;&#xFF0C;&#x63A5;&#x7740;&#x4ECE;&#x6700;&#x4F4E;&#x4F4D;&#x5F00;&#x59CB;&#xFF0C;&#x4F9D;&#x6B21;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
\1. &#x6309;&#x7167;&#x4E2A;&#x4F4D;&#x6570;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
\2. &#x6309;&#x7167;&#x5341;&#x4F4D;&#x6570;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
\3. &#x6309;&#x7167;&#x767E;&#x4F4D;&#x6570;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
&#x6392;&#x5E8F;&#x540E;&#xFF0C;&#x6570;&#x5217;&#x5C31;&#x53D8;&#x6210;&#x4E86;&#x4E00;&#x4E2A;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x3002;</p>
<p><strong>&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x4EE3;&#x7801;</strong></p>
<p><a href="javascript:void(0" target="_blank"><img src="https://common.cnblogs.com/images/copycode.gif" alt="&#x590D;&#x5236;&#x4EE3;&#x7801;"></a>;)</p>
<pre><code class="lang-c++"><span class="hljs-comment">/*
 * &#x83B7;&#x53D6;&#x6570;&#x7EC4;a&#x4E2D;&#x6700;&#x5927;&#x503C;
 *
 * &#x53C2;&#x6570;&#x8BF4;&#x660E;&#xFF1A;
 *     a -- &#x6570;&#x7EC4;
 *     n -- &#x6570;&#x7EC4;&#x957F;&#x5EA6;
 */</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">get_max</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> n)</span>
</span>{
    <span class="hljs-keyword">int</span> i, max;

    max = a[<span class="hljs-number">0</span>];
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>; i &lt; n; i++)
        <span class="hljs-keyword">if</span> (a[i] &gt; max)
            max = a[i];
    <span class="hljs-keyword">return</span> max;
}

<span class="hljs-comment">/*
 * &#x5BF9;&#x6570;&#x7EC4;&#x6309;&#x7167;&quot;&#x67D0;&#x4E2A;&#x4F4D;&#x6570;&quot;&#x8FDB;&#x884C;&#x6392;&#x5E8F;(&#x6876;&#x6392;&#x5E8F;)
 *
 * &#x53C2;&#x6570;&#x8BF4;&#x660E;&#xFF1A;
 *     a -- &#x6570;&#x7EC4;
 *     n -- &#x6570;&#x7EC4;&#x957F;&#x5EA6;
 *     exp -- &#x6307;&#x6570;&#x3002;&#x5BF9;&#x6570;&#x7EC4;a&#x6309;&#x7167;&#x8BE5;&#x6307;&#x6570;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
 *
 * &#x4F8B;&#x5982;&#xFF0C;&#x5BF9;&#x4E8E;&#x6570;&#x7EC4;a={50, 3, 542, 745, 2014, 154, 63, 616}&#xFF1B;
 *    (01) &#x5F53;exp=1&#x8868;&#x793A;&#x6309;&#x7167;&quot;&#x4E2A;&#x4F4D;&quot;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;
 *    (02) &#x5F53;exp=10&#x8868;&#x793A;&#x6309;&#x7167;&quot;&#x5341;&#x4F4D;&quot;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;
 *    (03) &#x5F53;exp=100&#x8868;&#x793A;&#x6309;&#x7167;&quot;&#x767E;&#x4F4D;&quot;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;
 *    ...
 */</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">count_sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> n, <span class="hljs-keyword">int</span> <span class="hljs-built_in">exp</span>)</span>
</span>{
    <span class="hljs-keyword">int</span> output[n];             <span class="hljs-comment">// &#x5B58;&#x50A8;&quot;&#x88AB;&#x6392;&#x5E8F;&#x6570;&#x636E;&quot;&#x7684;&#x4E34;&#x65F6;&#x6570;&#x7EC4;</span>
    <span class="hljs-keyword">int</span> i, buckets[<span class="hljs-number">10</span>] = {<span class="hljs-number">0</span>};

    <span class="hljs-comment">// &#x5C06;&#x6570;&#x636E;&#x51FA;&#x73B0;&#x7684;&#x6B21;&#x6570;&#x5B58;&#x50A8;&#x5728;buckets[]&#x4E2D;</span>
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; n; i++)
        buckets[ (a[i]/<span class="hljs-built_in">exp</span>)%<span class="hljs-number">10</span> ]++;

    <span class="hljs-comment">// &#x66F4;&#x6539;buckets[i]&#x3002;&#x76EE;&#x7684;&#x662F;&#x8BA9;&#x66F4;&#x6539;&#x540E;&#x7684;buckets[i]&#x7684;&#x503C;&#xFF0C;&#x662F;&#x8BE5;&#x6570;&#x636E;&#x5728;output[]&#x4E2D;&#x7684;&#x4F4D;&#x7F6E;&#x3002;</span>
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>; i &lt; <span class="hljs-number">10</span>; i++)
        buckets[i] += buckets[i - <span class="hljs-number">1</span>];

    <span class="hljs-comment">// &#x5C06;&#x6570;&#x636E;&#x5B58;&#x50A8;&#x5230;&#x4E34;&#x65F6;&#x6570;&#x7EC4;output[]&#x4E2D;</span>
    <span class="hljs-keyword">for</span> (i = n - <span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span>; i--)
    {
        output[buckets[ (a[i]/<span class="hljs-built_in">exp</span>)%<span class="hljs-number">10</span> ] - <span class="hljs-number">1</span>] = a[i];
        buckets[ (a[i]/<span class="hljs-built_in">exp</span>)%<span class="hljs-number">10</span> ]--;
    }

    <span class="hljs-comment">// &#x5C06;&#x6392;&#x5E8F;&#x597D;&#x7684;&#x6570;&#x636E;&#x8D4B;&#x503C;&#x7ED9;a[]</span>
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; n; i++)
        a[i] = output[i];
}

<span class="hljs-comment">/*
 * &#x57FA;&#x6570;&#x6392;&#x5E8F;
 *
 * &#x53C2;&#x6570;&#x8BF4;&#x660E;&#xFF1A;
 *     a -- &#x6570;&#x7EC4;
 *     n -- &#x6570;&#x7EC4;&#x957F;&#x5EA6;
 */</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">radix_sort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> n)</span>
</span>{
    <span class="hljs-keyword">int</span> <span class="hljs-built_in">exp</span>;    <span class="hljs-comment">// &#x6307;&#x6570;&#x3002;&#x5F53;&#x5BF9;&#x6570;&#x7EC4;&#x6309;&#x5404;&#x4F4D;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x65F6;&#xFF0C;exp=1&#xFF1B;&#x6309;&#x5341;&#x4F4D;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x65F6;&#xFF0C;exp=10&#xFF1B;...</span>
    <span class="hljs-keyword">int</span> max = get_max(a, n);    <span class="hljs-comment">// &#x6570;&#x7EC4;a&#x4E2D;&#x7684;&#x6700;&#x5927;&#x503C;</span>

    <span class="hljs-comment">// &#x4ECE;&#x4E2A;&#x4F4D;&#x5F00;&#x59CB;&#xFF0C;&#x5BF9;&#x6570;&#x7EC4;a&#x6309;&quot;&#x6307;&#x6570;&quot;&#x8FDB;&#x884C;&#x6392;&#x5E8F;</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-built_in">exp</span> = <span class="hljs-number">1</span>; max/<span class="hljs-built_in">exp</span> &gt; <span class="hljs-number">0</span>; <span class="hljs-built_in">exp</span> *= <span class="hljs-number">10</span>)
        count_sort(a, n, <span class="hljs-built_in">exp</span>);
}
</code></pre>
<p><a href="javascript:void(0" target="_blank"><img src="https://common.cnblogs.com/images/copycode.gif" alt="&#x590D;&#x5236;&#x4EE3;&#x7801;"></a>;)</p>
<p>radix_sort(a, n)&#x7684;&#x4F5C;&#x7528;&#x662F;&#x5BF9;&#x6570;&#x7EC4;a&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;</p>
<ol>
<li><p>&#x9996;&#x5148;&#x901A;&#x8FC7;get_max(a)&#x83B7;&#x53D6;&#x6570;&#x7EC4;a&#x4E2D;&#x7684;&#x6700;&#x5927;&#x503C;&#x3002;&#x83B7;&#x53D6;&#x6700;&#x5927;&#x503C;&#x7684;&#x76EE;&#x7684;&#x662F;&#x8BA1;&#x7B97;&#x51FA;&#x6570;&#x7EC4;a&#x7684;&#x6700;&#x5927;&#x6307;&#x6570;</p>
</li>
<li><p>&#x83B7;&#x53D6;&#x5230;&#x6570;&#x7EC4;a&#x4E2D;&#x7684;&#x6700;&#x5927;&#x6307;&#x6570;&#x4E4B;&#x540E;&#xFF0C;&#x518D;&#x4ECE;&#x6307;&#x6570;1&#x5F00;&#x59CB;&#xFF0C;&#x6839;&#x636E;&#x4F4D;&#x6570;&#x5BF9;&#x6570;&#x7EC4;a&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x5019;&#x91C7;&#x7528;&#x4E86;&#x6876;&#x6392;&#x5E8F;&#x3002;</p>
</li>
<li><p>count_sort(a, n, exp)&#x7684;&#x4F5C;&#x7528;&#x662F;&#x5BF9;&#x6570;&#x7EC4;a&#x6309;&#x7167;&#x6307;&#x6570;exp&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;
&#x4E0B;&#x9762;&#x7B80;&#x5355;&#x4ECB;&#x7ECD;&#x4E00;&#x4E0B;&#x5BF9;&#x6570;&#x7EC4;{53, 3, 542, 748, 14, 214, 154, 63, 616}&#x6309;&#x4E2A;&#x4F4D;&#x6570;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x7684;&#x6D41;&#x7A0B;&#x3002;
(01) &#x4E2A;&#x4F4D;&#x7684;&#x6570;&#x503C;&#x8303;&#x56F4;&#x662F;[0,10)&#x3002;&#x56E0;&#x6B64;&#xFF0C;&#x53C2;&#x89C1;&#x6876;&#x6570;&#x7EC4;buckets[]&#xFF0C;&#x5C06;&#x6570;&#x7EC4;&#x6309;&#x7167;&#x4E2A;&#x4F4D;&#x6570;&#x503C;&#x6DFB;&#x52A0;&#x5230;&#x6876;&#x4E2D;&#x3002;</p>
</li>
</ol>
<p><a href="https://images0.cnblogs.com/i/497634/201403/161839513552537.jpg" target="_blank"><img src="https://images0.cnblogs.com/i/497634/201403/161839513552537.jpg" alt="img"></a></p>
<p>(02) &#x63A5;&#x7740;&#x662F;&#x6839;&#x636E;&#x6876;&#x6570;&#x7EC4;buckets[]&#x6765;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x3002;&#x5047;&#x8BBE;&#x5C06;&#x6392;&#x5E8F;&#x540E;&#x7684;&#x6570;&#x7EC4;&#x5B58;&#x5728;output[]&#x4E2D;&#xFF1B;&#x627E;&#x51FA;output[]&#x548C;buckets[]&#x4E4B;&#x95F4;&#x7684;&#x8054;&#x7CFB;&#x5C31;&#x53EF;&#x4EE5;&#x5BF9;&#x6570;&#x636E;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#x4E86;&#x3002;</p>
<p><a href="https://images0.cnblogs.com/i/497634/201403/161840406685772.jpg" target="_blank"><img src="https://images0.cnblogs.com/i/497634/201403/161840406685772.jpg" alt="img"></a></p>
<h3 id="8&#x6876;&#x6392;&#x5E8F;"><a name="8&#x6876;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#8&#x6876;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="8&#x6876;&#x6392;&#x5E8F;" class="plugin-anchor" href="#8&#x6876;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>8.&#x6876;&#x6392;&#x5E8F;</h3>
<p>&#x4E00;&#x53E5;&#x8BDD;&#x603B;&#x7ED3;&#xFF1A;<strong>&#x5212;&#x5206;&#x591A;&#x4E2A;&#x8303;&#x56F4;&#x76F8;&#x540C;&#x7684;&#x533A;&#x95F4;&#xFF0C;&#x6BCF;&#x4E2A;&#x5B50;&#x533A;&#x95F4;&#x81EA;&#x6392;&#x5E8F;&#xFF0C;&#x6700;&#x540E;&#x5408;&#x5E76;</strong>&#x3002;</p>
<p>&#x6876;&#x6392;&#x5E8F;&#x662F;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x7684;&#x6269;&#x5C55;&#x7248;&#x672C;&#xFF0C;&#x8BA1;&#x6570;&#x6392;&#x5E8F;&#x53EF;&#x4EE5;&#x770B;&#x6210;&#x6BCF;&#x4E2A;&#x6876;&#x53EA;&#x5B58;&#x50A8;&#x76F8;&#x540C;&#x5143;&#x7D20;&#xFF0C;&#x800C;&#x6876;&#x6392;&#x5E8F;&#x6BCF;&#x4E2A;&#x6876;&#x5B58;&#x50A8;&#x4E00;&#x5B9A;&#x8303;&#x56F4;&#x7684;&#x5143;&#x7D20;&#xFF0C;&#x901A;&#x8FC7;&#x6620;&#x5C04;&#x51FD;&#x6570;&#xFF0C;&#x5C06;&#x5F85;&#x6392;&#x5E8F;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x6620;&#x5C04;&#x5230;&#x5404;&#x4E2A;&#x5BF9;&#x5E94;&#x7684;&#x6876;&#x4E2D;&#xFF0C;&#x5BF9;&#x6BCF;&#x4E2A;&#x6876;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x6392;&#x5E8F;&#xFF0C;&#x6700;&#x540E;&#x5C06;&#x975E;&#x7A7A;&#x6876;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x9010;&#x4E2A;&#x653E;&#x5165;&#x539F;&#x5E8F;&#x5217;&#x4E2D;&#x3002;</p>
<p>&#x6876;&#x6392;&#x5E8F;&#x9700;&#x8981;&#x5C3D;&#x91CF;&#x4FDD;&#x8BC1;&#x5143;&#x7D20;&#x5206;&#x6563;&#x5747;&#x5300;&#xFF0C;&#x5426;&#x5219;&#x5F53;&#x6240;&#x6709;&#x6570;&#x636E;&#x96C6;&#x4E2D;&#x5728;&#x540C;&#x4E00;&#x4E2A;&#x6876;&#x4E2D;&#x65F6;&#xFF0C;&#x6876;&#x6392;&#x5E8F;&#x5931;&#x6548;&#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130172245.png" alt="image-20201130172245339"></p>
<p><strong>&#x4E09;&#x3001;&#x6838;&#x5FC3;&#x4EE3;&#x7801;</strong></p>
<pre><code class="lang-java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">bucketSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] arr)</span></span>{

    <span class="hljs-comment">// &#x8BA1;&#x7B97;&#x6700;&#x5927;&#x503C;&#x4E0E;&#x6700;&#x5C0F;&#x503C;</span>
    <span class="hljs-keyword">int</span> max = Integer.MIN_VALUE;
    <span class="hljs-keyword">int</span> min = Integer.MAX_VALUE;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    <span class="hljs-comment">// &#x8BA1;&#x7B97;&#x6876;&#x7684;&#x6570;&#x91CF;</span>
    <span class="hljs-keyword">int</span> bucketNum = (max - min) / arr.length + <span class="hljs-number">1</span>;
    ArrayList&lt;ArrayList&lt;Integer&gt;&gt; bucketArr = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;(bucketNum);
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; bucketNum; i++){
        bucketArr.add(<span class="hljs-keyword">new</span> ArrayList&lt;Integer&gt;());
    }

    <span class="hljs-comment">// &#x5C06;&#x6BCF;&#x4E2A;&#x5143;&#x7D20;&#x653E;&#x5165;&#x6876;</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arr.length; i++){
        <span class="hljs-keyword">int</span> num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }

    <span class="hljs-comment">// &#x5BF9;&#x6BCF;&#x4E2A;&#x6876;&#x8FDB;&#x884C;&#x6392;&#x5E8F;</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }

    <span class="hljs-comment">// &#x5C06;&#x6876;&#x4E2D;&#x7684;&#x5143;&#x7D20;&#x8D4B;&#x503C;&#x5230;&#x539F;&#x5E8F;&#x5217;</span>
    <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; bucketArr.size(); i++){
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; bucketArr.get(i).size(); j++){
            arr[index++] = bucketArr.get(i).get(j);
        }
    }  
}
</code></pre>
<h3 id="9&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;"><a name="9&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#9&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="9&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;" class="plugin-anchor" href="#9&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>9.&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x6392;&#x5E8F;</h3>
<p>&#x5C06;&#x4E00;&#x4E2A;&#x8BB0;&#x5F55;&#x63D2;&#x5165;&#x5230;&#x5DF2;&#x6392;&#x597D;&#x5E8F;&#x7684;&#x5E8F;&#x5217;&#x4E2D;&#xFF0C;&#x4ECE;&#x800C;&#x5F97;&#x5230;&#x4E00;&#x4E2A;&#x65B0;&#x7684;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#xFF08;&#x5C06;&#x5E8F;&#x5217;&#x7684;&#x7B2C;&#x4E00;&#x4E2A;&#x6570;&#x636E;&#x770B;&#x6210;&#x662F;&#x4E00;&#x4E2A;&#x6709;&#x5E8F;&#x7684;&#x5B50;&#x5E8F;&#x5217;&#xFF0C;&#x7136;&#x540E;&#x4ECE;&#x7B2C;&#x4E8C;&#x4E2A;&#x8BB0;&#x5F55;&#x9010;&#x4E2A;&#x5411;&#x8BE5;&#x6709;&#x5E8F;&#x7684;&#x5B50;&#x5E8F;&#x5217;&#x8FDB;&#x884C;&#x6709;&#x5E8F;&#x7684;&#x63D2;&#x5165;&#xFF0C;&#x76F4;&#x81F3;&#x6574;&#x4E2A;&#x5E8F;&#x5217;&#x6709;&#x5E8F;&#xFF09;</p>
<p>&#x91CD;&#x70B9;&#xFF1A;&#x4F7F;&#x7528;&#x54E8;&#x5175;&#xFF0C;&#x7528;&#x4E8E;&#x4E34;&#x65F6;&#x5B58;&#x50A8;&#x548C;&#x5224;&#x65AD;&#x6570;&#x7EC4;&#x8FB9;&#x754C;&#x3002;</p>
<p><strong>2 &#x6392;&#x5E8F;&#x6D41;&#x7A0B;&#x56FE;</strong></p>
<p><img src="https:////upload-images.jianshu.io/upload_images/11016594-150b6c462e3ed809.png?imageMogr2/auto-orient/strip|imageView2/2/w/471/format/webp" alt="img"></p>
<p><strong>3&#x7B97;&#x6CD5;&#x5B9E;&#x73B0; java</strong></p>
<pre><code class="lang-java"><span class="hljs-keyword">import</span> java.util.Arrays;

<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Sort</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{

        <span class="hljs-keyword">int</span> arr[] = {<span class="hljs-number">2</span>,<span class="hljs-number">1</span>,<span class="hljs-number">5</span>,<span class="hljs-number">3</span>,<span class="hljs-number">6</span>,<span class="hljs-number">4</span>,<span class="hljs-number">9</span>,<span class="hljs-number">8</span>,<span class="hljs-number">7</span>};

        <span class="hljs-keyword">int</span> temp;

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;arr.length;i++){

            <span class="hljs-comment">//&#x5F85;&#x6392;&#x5143;&#x7D20;&#x5C0F;&#x4E8E;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x65F6;&#xFF0C;&#x5411;&#x524D;&#x63D2;&#x5165;</span>
            <span class="hljs-keyword">if</span> (arr[i]&lt;arr[i-<span class="hljs-number">1</span>]){
                temp = arr[i];
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j=i;j&gt;=<span class="hljs-number">0</span>;j--){
                    <span class="hljs-keyword">if</span> (j&gt;<span class="hljs-number">0</span> &amp;&amp; arr[j-<span class="hljs-number">1</span>]&gt;temp) {
                        arr[j]=arr[j-<span class="hljs-number">1</span>];
                    }<span class="hljs-keyword">else</span> {
                        arr[j]=temp;
                        <span class="hljs-keyword">break</span>;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(arr));

    }


}
</code></pre>
<p><strong>4 &#x8FD0;&#x884C;&#x7ED3;&#x679C;</strong></p>
<p><img src="https:////upload-images.jianshu.io/upload_images/11016594-99e70648ddb4b690.png?imageMogr2/auto-orient/strip|imageView2/2/w/477/format/webp" alt="img"></p>
<h3 id="10&#x603B;&#x7ED3;"><a name="10&#x603B;&#x7ED3;" class="anchor-navigation-ex-anchor" href="#10&#x603B;&#x7ED3;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="10&#x603B;&#x7ED3;" class="plugin-anchor" href="#10&#x603B;&#x7ED3;"><i class="fa fa-link" aria-hidden="true"></i></a>10.&#x603B;&#x7ED3;</h3>
<h4 id="&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;"><a name="&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;" class="anchor-navigation-ex-anchor" href="#&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;" class="plugin-anchor" href="#&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;</h4>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201130195516.png" alt="image-20201130195516125"></p>
<h4 id="&#x7A33;&#x5B9A;&#x6027;&#x5206;&#x6790;"><a name="&#x7A33;&#x5B9A;&#x6027;&#x5206;&#x6790;" class="anchor-navigation-ex-anchor" href="#&#x7A33;&#x5B9A;&#x6027;&#x5206;&#x6790;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x7A33;&#x5B9A;&#x6027;&#x5206;&#x6790;" class="plugin-anchor" href="#&#x7A33;&#x5B9A;&#x6027;&#x5206;&#x6790;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x7A33;&#x5B9A;&#x6027;&#x5206;&#x6790;</h4>
<p> &#x9996;&#x5148;&#xFF0C;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x7A33;&#x5B9A;&#x6027;&#x5927;&#x5BB6;&#x5E94;&#x8BE5;&#x90FD;&#x77E5;&#x9053;&#xFF0C;&#x901A;&#x4FD7;&#x5730;&#x8BB2;&#x5C31;&#x662F;&#x80FD;&#x4FDD;&#x8BC1;&#x6392;&#x5E8F;&#x524D;2&#x4E2A;&#x76F8;&#x7B49;&#x7684;&#x6570;&#x5176;&#x5728;&#x5E8F;&#x5217;&#x7684;&#x524D;&#x540E;&#x4F4D;&#x7F6E;&#x987A;&#x5E8F;&#x548C;&#x6392;&#x5E8F;&#x540E;&#x5B83;&#x4EEC;&#x4E24;&#x4E2A;&#x7684;&#x524D;&#x540E;&#x4F4D;&#x7F6E;&#x987A;&#x5E8F;&#x76F8;&#x540C;&#x3002;&#x5728;&#x7B80;&#x5355;&#x5F62;&#x5F0F;&#x5316;&#x4E00;&#x4E0B;&#xFF0C;&#x5982;&#x679C;Ai = Aj, Ai&#x539F;&#x6765;&#x5728;&#x4F4D;&#x7F6E;&#x524D;&#xFF0C;&#x6392;&#x5E8F;&#x540E;Ai&#x8FD8;&#x662F;&#x8981;&#x5728;Aj&#x4F4D;&#x7F6E;&#x524D;&#x3002;</p>
<p>   &#x5176;&#x6B21;&#xFF0C;&#x8BF4;&#x4E00;&#x4E0B;&#x7A33;&#x5B9A;&#x6027;&#x7684;&#x597D;&#x5904;&#x3002;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x5982;&#x679C;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#xFF0C;&#x90A3;&#x4E48;&#x4ECE;&#x4E00;&#x4E2A;&#x952E;&#x4E0A;&#x6392;&#x5E8F;&#xFF0C;&#x7136;&#x540E;&#x518D;&#x4ECE;&#x53E6;&#x4E00;&#x4E2A;&#x952E;&#x4E0A;&#x6392;&#x5E8F;&#xFF0C;&#x7B2C;&#x4E00;&#x4E2A;&#x952E;&#x6392;&#x5E8F;&#x7684;&#x7ED3;&#x679C;&#x53EF;&#x4EE5;&#x4E3A;&#x7B2C;&#x4E8C;&#x4E2A;&#x952E;&#x6392;&#x5E8F;&#x6240;&#x7528;&#x3002;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x5C31; &#x662F;&#x8FD9;&#x6837;&#xFF0C;&#x5148;&#x6309;&#x4F4E;&#x4F4D;&#x6392;&#x5E8F;&#xFF0C;&#x9010;&#x6B21;&#x6309;&#x9AD8;&#x4F4D;&#x6392;&#x5E8F;&#xFF0C;&#x4F4E;&#x4F4D;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x5176;&#x987A;&#x5E8F;&#x518D;&#x9AD8;&#x4F4D;&#x4E5F;&#x76F8;&#x540C;&#x65F6;&#x662F;&#x4E0D;&#x4F1A;&#x6539;&#x53D8;&#x7684;&#x3002;&#x53E6;&#x5916;&#xFF0C;&#x5982;&#x679C;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7A33;&#x5B9A;&#xFF0C;&#x5BF9;&#x57FA;&#x4E8E;&#x6BD4;&#x8F83;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x800C;&#x8A00;&#xFF0C;&#x5143;&#x7D20;&#x4EA4;&#x6362; &#x7684;&#x6B21;&#x6570;&#x53EF;&#x80FD;&#x4F1A;&#x5C11;&#x4E00;&#x4E9B;(&#x4E2A;&#x4EBA;&#x611F;&#x89C9;&#xFF0C;&#x6CA1;&#x6709;&#x8BC1;&#x5B9E;)&#x3002;</p>
<p>   &#x56DE;&#x5230;&#x4E3B;&#x9898;&#xFF0C;&#x73B0;&#x5728;&#x5206;&#x6790;&#x4E00;&#x4E0B;&#x5E38;&#x89C1;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x7684;&#x7A33;&#x5B9A;&#x6027;&#xFF0C;&#x6BCF;&#x4E2A;&#x90FD;&#x7ED9;&#x51FA;&#x7B80;&#x5355;&#x7684;&#x7406;&#x7531;&#x3002;</p>
<p>  (1)&#x5192;&#x6CE1;&#x6392;&#x5E8F;</p>
<p>&#x200B;    &#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x5C31;&#x662F;&#x628A;&#x5C0F;&#x7684;&#x5143;&#x7D20;&#x5F80;&#x524D;&#x8C03;&#x6216;&#x8005;&#x628A;&#x5927;&#x7684;&#x5143;&#x7D20;&#x5F80;&#x540E;&#x8C03;&#x3002;&#x6BD4;&#x8F83;&#x662F;&#x76F8;&#x90BB;&#x7684;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x6BD4;&#x8F83;&#xFF0C;&#x4EA4;&#x6362;&#x4E5F;&#x53D1;&#x751F;&#x5728;&#x8FD9;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x5982;&#x679C;&#x4E24;&#x4E2A;&#x5143;&#x7D20;&#x76F8;&#x7B49;&#xFF0C;&#x6211;&#x60F3;&#x4F60;&#x662F;&#x4E0D;&#x4F1A;&#x518D;&#x65E0; &#x804A;&#x5730;&#x628A;&#x4ED6;&#x4EEC;&#x4FE9;&#x4EA4;&#x6362;&#x4E00;&#x4E0B;&#x7684;&#xFF1B;&#x5982;&#x679C;&#x4E24;&#x4E2A;&#x76F8;&#x7B49;&#x7684;&#x5143;&#x7D20;&#x6CA1;&#x6709;&#x76F8;&#x90BB;&#xFF0C;&#x90A3;&#x4E48;&#x5373;&#x4F7F;&#x901A;&#x8FC7;&#x524D;&#x9762;&#x7684;&#x4E24;&#x4E24;&#x4EA4;&#x6362;&#x628A;&#x4E24;&#x4E2A;&#x76F8;&#x90BB;&#x8D77;&#x6765;&#xFF0C;&#x8FD9;&#x65F6;&#x5019;&#x4E5F;&#x4E0D;&#x4F1A;&#x4EA4;&#x6362;&#xFF0C;&#x6240;&#x4EE5;&#x76F8;&#x540C;&#x5143;&#x7D20;&#x7684;&#x524D;&#x540E;&#x987A;&#x5E8F;&#x5E76;&#x6CA1;&#x6709;&#x6539; &#x53D8;&#xFF0C;&#x6240;&#x4EE5;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x662F;&#x4E00;&#x79CD;&#x7A33;&#x5B9A;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p>(2)&#x9009;&#x62E9;&#x6392;&#x5E8F;</p>
<p>   &#x9009;&#x62E9;&#x6392;&#x5E8F;&#x662F;&#x7ED9;&#x6BCF;&#x4E2A;&#x4F4D;&#x7F6E;&#x9009;&#x62E9;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x6700;&#x5C0F;&#x7684;&#xFF0C;&#x6BD4;&#x5982;&#x7ED9;&#x7B2C;&#x4E00;&#x4E2A;&#x4F4D;&#x7F6E;&#x9009;&#x62E9;&#x6700;&#x5C0F;&#x7684;&#xFF0C;&#x5728;&#x5269;&#x4F59;&#x5143;&#x7D20;&#x91CC;&#x9762;&#x7ED9;&#x7B2C;&#x4E8C;&#x4E2A;&#x5143;&#x7D20;&#x9009;&#x62E9;&#x7B2C;&#x4E8C;&#x5C0F;&#x7684;&#xFF0C;&#x4F9D;&#x6B21;&#x7C7B;&#x63A8;&#xFF0C;&#x76F4;&#x5230;&#x7B2C;n-1&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x7B2C;n&#x4E2A; &#x5143;&#x7D20;&#x4E0D;&#x7528;&#x9009;&#x62E9;&#x4E86;&#xFF0C;&#x56E0;&#x4E3A;&#x53EA;&#x5269;&#x4E0B;&#x5B83;&#x4E00;&#x4E2A;&#x6700;&#x5927;&#x7684;&#x5143;&#x7D20;&#x4E86;&#x3002;&#x90A3;&#x4E48;&#xFF0C;&#x5728;&#x4E00;&#x8D9F;&#x9009;&#x62E9;&#xFF0C;&#x5982;&#x679C;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x6BD4;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x5C0F;&#xFF0C;&#x800C;&#x8BE5;&#x5C0F;&#x7684;&#x5143;&#x7D20;&#x53C8;&#x51FA;&#x73B0;&#x5728;&#x4E00;&#x4E2A;&#x548C;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x76F8;&#x7B49;&#x7684;&#x5143;&#x7D20;&#x540E;&#x9762;&#xFF0C;&#x90A3;&#x4E48; &#x4EA4;&#x6362;&#x540E;&#x7A33;&#x5B9A;&#x6027;&#x5C31;&#x88AB;&#x7834;&#x574F;&#x4E86;&#x3002;&#x6BD4;&#x8F83;&#x62D7;&#x53E3;&#xFF0C;&#x4E3E;&#x4E2A;&#x4F8B;&#x5B50;&#xFF0C;&#x5E8F;&#x5217;5 8 5 2 9&#xFF0C; &#x6211;&#x4EEC;&#x77E5;&#x9053;&#x7B2C;&#x4E00;&#x904D;&#x9009;&#x62E9;&#x7B2C;1&#x4E2A;&#x5143;&#x7D20;5&#x4F1A;&#x548C;2&#x4EA4;&#x6362;&#xFF0C;&#x90A3;&#x4E48;&#x539F;&#x5E8F;&#x5217;&#x4E2D;2&#x4E2A;5&#x7684;&#x76F8;&#x5BF9;&#x524D;&#x540E;&#x987A;&#x5E8F;&#x5C31;&#x88AB;&#x7834;&#x574F;&#x4E86;&#xFF0C;&#x6240;&#x4EE5;&#x9009;&#x62E9;&#x6392;&#x5E8F;&#x4E0D;&#x662F;&#x4E00;&#x4E2A;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p>(3)&#x63D2;&#x5165;&#x6392;&#x5E8F;
   &#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x5728;&#x4E00;&#x4E2A;&#x5DF2;&#x7ECF;&#x6709;&#x5E8F;&#x7684;&#x5C0F;&#x5E8F;&#x5217;&#x7684;&#x57FA;&#x7840;&#x4E0A;&#xFF0C;&#x4E00;&#x6B21;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x3002;&#x5F53;&#x7136;&#xFF0C;&#x521A;&#x5F00;&#x59CB;&#x8FD9;&#x4E2A;&#x6709;&#x5E8F;&#x7684;&#x5C0F;&#x5E8F;&#x5217;&#x53EA;&#x6709;1&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x5C31;&#x662F;&#x7B2C;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x3002;&#x6BD4;&#x8F83;&#x662F;&#x4ECE;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x7684;&#x672B;&#x5C3E;&#x5F00; &#x59CB;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x60F3;&#x8981;&#x63D2;&#x5165;&#x7684;&#x5143;&#x7D20;&#x548C;&#x5DF2;&#x7ECF;&#x6709;&#x5E8F;&#x7684;&#x6700;&#x5927;&#x8005;&#x5F00;&#x59CB;&#x6BD4;&#x8D77;&#xFF0C;&#x5982;&#x679C;&#x6BD4;&#x5B83;&#x5927;&#x5219;&#x76F4;&#x63A5;&#x63D2;&#x5165;&#x5728;&#x5176;&#x540E;&#x9762;&#xFF0C;&#x5426;&#x5219;&#x4E00;&#x76F4;&#x5F80;&#x524D;&#x627E;&#x76F4;&#x5230;&#x627E;&#x5230;&#x5B83;&#x8BE5;&#x63D2;&#x5165;&#x7684;&#x4F4D;&#x7F6E;&#x3002;&#x5982;&#x679C;&#x78B0;&#x89C1;&#x4E00;&#x4E2A;&#x548C;&#x63D2;&#x5165;&#x5143;&#x7D20;&#x76F8; &#x7B49;&#x7684;&#xFF0C;&#x90A3;&#x4E48;&#x63D2;&#x5165;&#x5143;&#x7D20;&#x628A;&#x60F3;&#x63D2;&#x5165;&#x7684;&#x5143;&#x7D20;&#x653E;&#x5728;&#x76F8;&#x7B49;&#x5143;&#x7D20;&#x7684;&#x540E;&#x9762;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x76F8;&#x7B49;&#x5143;&#x7D20;&#x7684;&#x524D;&#x540E;&#x987A;&#x5E8F;&#x6CA1;&#x6709;&#x6539;&#x53D8;&#xFF0C;&#x4ECE;&#x539F;&#x65E0;&#x5E8F;&#x5E8F;&#x5217;&#x51FA;&#x53BB;&#x7684;&#x987A;&#x5E8F;&#x5C31;&#x662F;&#x6392;&#x597D;&#x5E8F;&#x540E;&#x7684;&#x987A;&#x5E8F;&#xFF0C;&#x6240;&#x4EE5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x7A33; &#x5B9A;&#x7684;&#x3002;</p>
<p>(4)&#x5FEB;&#x901F;&#x6392;&#x5E8F;
  &#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x6709;&#x4E24;&#x4E2A;&#x65B9;&#x5411;&#xFF0C;&#x5DE6;&#x8FB9;&#x7684;i&#x4E0B;&#x6807;&#x4E00;&#x76F4;&#x5F80;&#x53F3;&#x8D70;&#xFF0C;&#x5F53;a[i] &lt;= a[center_index]&#xFF0C;&#x5176;&#x4E2D;center_index&#x662F;&#x4E2D;&#x67A2;&#x5143;&#x7D20;&#x7684;&#x6570;&#x7EC4;&#x4E0B;&#x6807;&#xFF0C;&#x4E00;&#x822C;&#x53D6;&#x4E3A;&#x6570;&#x7EC4;&#x7B2C;0&#x4E2A;&#x5143;&#x7D20;&#x3002;&#x800C;&#x53F3;&#x8FB9;&#x7684;j&#x4E0B;&#x6807;&#x4E00;&#x76F4;&#x5F80;&#x5DE6;&#x8D70;&#xFF0C;&#x5F53;a[j] &gt; a[center_index]&#x3002;&#x5982;&#x679C;i&#x548C;j&#x90FD;&#x8D70;&#x4E0D;&#x52A8;&#x4E86;&#xFF0C;i &lt;= j, &#x4EA4;&#x6362;a[i]&#x548C;a[j],&#x91CD;&#x590D;&#x4E0A;&#x9762;&#x7684;&#x8FC7;&#x7A0B;&#xFF0C;&#x76F4;&#x5230;i&gt;j&#x3002; &#x4EA4;&#x6362;a[j]&#x548C;a[center_index]&#xFF0C;&#x5B8C;&#x6210;&#x4E00;&#x8D9F;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x3002;&#x5728;&#x4E2D;&#x67A2;&#x5143;&#x7D20;&#x548C;a[j]&#x4EA4;&#x6362;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x5F88;&#x6709;&#x53EF;&#x80FD;&#x628A;&#x524D;&#x9762;&#x7684;&#x5143;&#x7D20;&#x7684;&#x7A33;&#x5B9A;&#x6027;&#x6253;&#x4E71;&#xFF0C;&#x6BD4;&#x5982;&#x5E8F;&#x5217;&#x4E3A; 5 3 3 4 3 8 9 10 11&#xFF0C; &#x73B0;&#x5728;&#x4E2D;&#x67A2;&#x5143;&#x7D20;5&#x548C;3(&#x7B2C;5&#x4E2A;&#x5143;&#x7D20;&#xFF0C;&#x4E0B;&#x6807;&#x4ECE;1&#x5F00;&#x59CB;&#x8BA1;)&#x4EA4;&#x6362;&#x5C31;&#x4F1A;&#x628A;&#x5143;&#x7D20;3&#x7684;&#x7A33;&#x5B9A;&#x6027;&#x6253;&#x4E71;&#xFF0C;&#x6240;&#x4EE5;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x662F;&#x4E00;&#x4E2A;&#x4E0D;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x4E0D;&#x7A33;&#x5B9A;&#x53D1;&#x751F;&#x5728;&#x4E2D;&#x67A2;&#x5143;&#x7D20;&#x548C;a[j] &#x4EA4;&#x6362;&#x7684;&#x65F6;&#x523B;&#x3002;</p>
<p>(5)&#x5F52;&#x5E76;&#x6392;&#x5E8F;
  &#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x662F;&#x628A;&#x5E8F;&#x5217;&#x9012;&#x5F52;&#x5730;&#x5206;&#x6210;&#x77ED;&#x5E8F;&#x5217;&#xFF0C;&#x9012;&#x5F52;&#x51FA;&#x53E3;&#x662F;&#x77ED;&#x5E8F;&#x5217;&#x53EA;&#x6709;1&#x4E2A;&#x5143;&#x7D20;(&#x8BA4;&#x4E3A;&#x76F4;&#x63A5;&#x6709;&#x5E8F;)&#x6216;&#x8005;2&#x4E2A;&#x5E8F;&#x5217;(1&#x6B21;&#x6BD4;&#x8F83;&#x548C;&#x4EA4;&#x6362;),&#x7136;&#x540E;&#x628A;&#x5404;&#x4E2A;&#x6709;&#x5E8F;&#x7684;&#x6BB5;&#x5E8F;&#x5217;&#x5408;&#x5E76;&#x6210;&#x4E00;&#x4E2A;&#x6709; &#x5E8F;&#x7684;&#x957F;&#x5E8F;&#x5217;&#xFF0C;&#x4E0D;&#x65AD;&#x5408;&#x5E76;&#x76F4;&#x5230;&#x539F;&#x5E8F;&#x5217;&#x5168;&#x90E8;&#x6392;&#x597D;&#x5E8F;&#x3002;&#x53EF;&#x4EE5;&#x53D1;&#x73B0;&#xFF0C;&#x5728;1&#x4E2A;&#x6216;2&#x4E2A;&#x5143;&#x7D20;&#x65F6;&#xFF0C;1&#x4E2A;&#x5143;&#x7D20;&#x4E0D;&#x4F1A;&#x4EA4;&#x6362;&#xFF0C;2&#x4E2A;&#x5143;&#x7D20;&#x5982;&#x679C;&#x5927;&#x5C0F;&#x76F8;&#x7B49;&#x4E5F;&#x6CA1;&#x6709;&#x4EBA;&#x6545;&#x610F;&#x4EA4;&#x6362;&#xFF0C;&#x8FD9;&#x4E0D;&#x4F1A;&#x7834;&#x574F;&#x7A33;&#x5B9A; &#x6027;&#x3002;&#x90A3;&#x4E48;&#xFF0C;&#x5728;&#x77ED;&#x7684;&#x6709;&#x5E8F;&#x5E8F;&#x5217;&#x5408;&#x5E76;&#x7684;&#x8FC7;&#x7A0B;&#x4E2D;&#xFF0C;&#x7A33;&#x5B9A;&#x662F;&#x662F;&#x5426;&#x53D7;&#x5230;&#x7834;&#x574F;&#xFF1F;&#x6CA1;&#x6709;&#xFF0C;&#x5408;&#x5E76;&#x8FC7;&#x7A0B;&#x4E2D;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x4FDD;&#x8BC1;&#x5982;&#x679C;&#x4E24;&#x4E2A;&#x5F53;&#x524D;&#x5143;&#x7D20;&#x76F8;&#x7B49;&#x65F6;&#xFF0C;&#x6211;&#x4EEC;&#x628A;&#x5904;&#x5728;&#x524D;&#x9762;&#x7684;&#x5E8F;&#x5217;&#x7684;&#x5143;&#x7D20;&#x4FDD;&#x5B58;&#x5728;&#x7ED3; &#x679C;&#x5E8F;&#x5217;&#x7684;&#x524D;&#x9762;&#xFF0C;&#x8FD9;&#x6837;&#x5C31;&#x4FDD;&#x8BC1;&#x4E86;&#x7A33;&#x5B9A;&#x6027;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x4E5F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p>(6)&#x57FA;&#x6570;&#x6392;&#x5E8F;
  &#x57FA;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x6309;&#x7167;&#x4F4E;&#x4F4D;&#x5148;&#x6392;&#x5E8F;&#xFF0C;&#x7136;&#x540E;&#x6536;&#x96C6;&#xFF1B;&#x518D;&#x6309;&#x7167;&#x9AD8;&#x4F4D;&#x6392;&#x5E8F;&#xFF0C;&#x7136;&#x540E;&#x518D;&#x6536;&#x96C6;&#xFF1B;&#x4F9D;&#x6B21;&#x7C7B;&#x63A8;&#xFF0C;&#x76F4;&#x5230;&#x6700;&#x9AD8;&#x4F4D;&#x3002;&#x6709;&#x65F6;&#x5019;&#x6709;&#x4E9B;&#x5C5E;&#x6027;&#x662F;&#x6709;&#x4F18;&#x5148;&#x7EA7;&#x987A;&#x5E8F;&#x7684;&#xFF0C;&#x5148;&#x6309;&#x4F4E;&#x4F18;&#x5148;&#x7EA7;&#x6392;&#x5E8F;&#xFF0C;&#x518D;&#x6309;&#x9AD8;&#x4F18; &#x5148;&#x7EA7;&#x6392;&#x5E8F;&#xFF0C;&#x6700;&#x540E;&#x7684;&#x6B21;&#x5E8F;&#x5C31;&#x662F;&#x9AD8;&#x4F18;&#x5148;&#x7EA7;&#x9AD8;&#x7684;&#x5728;&#x524D;&#xFF0C;&#x9AD8;&#x4F18;&#x5148;&#x7EA7;&#x76F8;&#x540C;&#x7684;&#x4F4E;&#x4F18;&#x5148;&#x7EA7;&#x9AD8;&#x7684;&#x5728;&#x524D;&#x3002;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x57FA;&#x4E8E;&#x5206;&#x522B;&#x6392;&#x5E8F;&#xFF0C;&#x5206;&#x522B;&#x6536;&#x96C6;&#xFF0C;&#x6240;&#x4EE5;&#x5176;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p>(7)&#x5E0C;&#x5C14;&#x6392;&#x5E8F;(shell)
  &#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x662F;&#x6309;&#x7167;&#x4E0D;&#x540C;&#x6B65;&#x957F;&#x5BF9;&#x5143;&#x7D20;&#x8FDB;&#x884C;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF0C;&#x5F53;&#x521A;&#x5F00;&#x59CB;&#x5143;&#x7D20;&#x5F88;&#x65E0;&#x5E8F;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x6B65;&#x957F;&#x6700;&#x5927;&#xFF0C;&#x6240;&#x4EE5;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x7684;&#x5143;&#x7D20;&#x4E2A;&#x6570;&#x5F88;&#x5C11;&#xFF0C;&#x901F;&#x5EA6;&#x5F88;&#x5FEB;&#xFF1B;&#x5F53;&#x5143;&#x7D20;&#x57FA;&#x672C;&#x6709;&#x5E8F;&#x4E86;&#xFF0C;&#x6B65;&#x957F;&#x5F88;&#x5C0F;&#xFF0C; &#x63D2;&#x5165;&#x6392;&#x5E8F;&#x5BF9;&#x4E8E;&#x6709;&#x5E8F;&#x7684;&#x5E8F;&#x5217;&#x6548;&#x7387;&#x5F88;&#x9AD8;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4F1A;&#x6BD4;o(n^2)&#x597D;&#x4E00;&#x4E9B;&#x3002;&#x7531;&#x4E8E;&#x591A;&#x6B21;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#xFF0C;&#x6211;&#x4EEC;&#x77E5;&#x9053;&#x4E00;&#x6B21;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#xFF0C;&#x4E0D;&#x4F1A;&#x6539;&#x53D8;&#x76F8;&#x540C;&#x5143; &#x7D20;&#x7684;&#x76F8;&#x5BF9;&#x987A;&#x5E8F;&#xFF0C;&#x4F46;&#x5728;&#x4E0D;&#x540C;&#x7684;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x8FC7;&#x7A0B;&#x4E2D;&#xFF0C;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x53EF;&#x80FD;&#x5728;&#x5404;&#x81EA;&#x7684;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x4E2D;&#x79FB;&#x52A8;&#xFF0C;&#x6700;&#x540E;&#x5176;&#x7A33;&#x5B9A;&#x6027;&#x5C31;&#x4F1A;&#x88AB;&#x6253;&#x4E71;&#xFF0C;&#x6240;&#x4EE5;shell&#x6392;&#x5E8F;&#x662F;&#x4E0D;&#x7A33;&#x5B9A;&#x7684;&#x3002;</p>
<p>(8)&#x5806;&#x6392;&#x5E8F;
  &#x6211;&#x4EEC;&#x77E5;&#x9053;&#x5806;&#x7684;&#x7ED3;&#x6784;&#x662F;&#x8282;&#x70B9;i&#x7684;&#x5B69;&#x5B50;&#x4E3A;2<em>i&#x548C;2</em>i+1&#x8282;&#x70B9;&#xFF0C;&#x5927;&#x9876;&#x5806;&#x8981;&#x6C42;&#x7236;&#x8282;&#x70B9;&#x5927;&#x4E8E;&#x7B49;&#x4E8E;&#x5176;2&#x4E2A;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x5C0F;&#x9876;&#x5806;&#x8981;&#x6C42;&#x7236;&#x8282;&#x70B9;&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E;&#x5176;2&#x4E2A;&#x5B50;&#x8282;&#x70B9;&#x3002;&#x5728;&#x4E00;&#x4E2A;&#x957F;&#x4E3A;n &#x7684;&#x5E8F;&#x5217;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x7684;&#x8FC7;&#x7A0B;&#x662F;&#x4ECE;&#x7B2C;n/2&#x5F00;&#x59CB;&#x548C;&#x5176;&#x5B50;&#x8282;&#x70B9;&#x5171;3&#x4E2A;&#x503C;&#x9009;&#x62E9;&#x6700;&#x5927;(&#x5927;&#x9876;&#x5806;)&#x6216;&#x8005;&#x6700;&#x5C0F;(&#x5C0F;&#x9876;&#x5806;),&#x8FD9;3&#x4E2A;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x9009;&#x62E9;&#x5F53;&#x7136;&#x4E0D;&#x4F1A;&#x7834;&#x574F;&#x7A33;&#x5B9A;&#x6027;&#x3002;&#x4F46;&#x5F53;&#x4E3A;n /2-1, n/2-2, ...1&#x8FD9;&#x4E9B;&#x4E2A;&#x7236;&#x8282;&#x70B9;&#x9009;&#x62E9;&#x5143;&#x7D20;&#x65F6;&#xFF0C;&#x5C31;&#x4F1A;&#x7834;&#x574F;&#x7A33;&#x5B9A;&#x6027;&#x3002;&#x6709;&#x53EF;&#x80FD;&#x7B2C;n/2&#x4E2A;&#x7236;&#x8282;&#x70B9;&#x4EA4;&#x6362;&#x628A;&#x540E;&#x9762;&#x4E00;&#x4E2A;&#x5143;&#x7D20;&#x4EA4;&#x6362;&#x8FC7;&#x53BB;&#x4E86;&#xFF0C;&#x800C;&#x7B2C;n/2-1&#x4E2A;&#x7236;&#x8282;&#x70B9;&#x628A;&#x540E;&#x9762;&#x4E00;&#x4E2A;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x6CA1; &#x6709;&#x4EA4;&#x6362;&#xFF0C;&#x90A3;&#x4E48;&#x8FD9;2&#x4E2A;&#x76F8;&#x540C;&#x7684;&#x5143;&#x7D20;&#x4E4B;&#x95F4;&#x7684;&#x7A33;&#x5B9A;&#x6027;&#x5C31;&#x88AB;&#x7834;&#x574F;&#x4E86;&#x3002;&#x6240;&#x4EE5;&#xFF0C;&#x5806;&#x6392;&#x5E8F;&#x4E0D;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p>&#x7EFC;&#x4E0A;&#xFF0C;&#x5F97;&#x51FA;&#x7ED3;&#x8BBA;: &#x9009;&#x62E9;&#x6392;&#x5E8F;&#x3001;&#x5FEB;&#x901F;&#x6392;&#x5E8F;&#x3001;&#x5E0C;&#x5C14;&#x6392;&#x5E8F;&#x3001;&#x5806;&#x6392;&#x5E8F;&#x4E0D;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#xFF0C;&#x800C;&#x5192;&#x6CE1;&#x6392;&#x5E8F;&#x3001;&#x63D2;&#x5165;&#x6392;&#x5E8F;&#x3001;&#x5F52;&#x5E76;&#x6392;&#x5E8F;&#x548C;&#x57FA;&#x6570;&#x6392;&#x5E8F;&#x662F;&#x7A33;&#x5B9A;&#x7684;&#x6392;&#x5E8F;&#x7B97;&#x6CD5;&#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201221224141.png" alt="image-20201221224140991"></p>

<script>console.log("plugin-popup....");document.onclick = function(e){ e.target.tagName === "IMG" && window.open(e.target.src,e.target.src)}</script><style>img{cursor:pointer}</style>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="3.散列表.html" class="navigation navigation-prev " aria-label="Previous page: 3.散列表">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="5.排序列题.html" class="navigation navigation-next " aria-label="Next page: 5.排序算法例题">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"4.排序算法","level":"3.4","depth":1,"next":{"title":"5.排序算法例题","level":"3.5","depth":1,"path":"数据结构/5.排序列题.md","ref":"数据结构/5.排序列题.md","articles":[]},"previous":{"title":"3.散列表","level":"3.3","depth":1,"path":"数据结构/3.散列表.md","ref":"数据结构/3.散列表.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-sharing","splitter","expandable-chapters-small","anchors","sharing-plus","anchor-navigation-ex","favicon","expandable-chapters","toggle-chapters","back-to-top-button","code","-lunr","-search","search-pro","pageview-count","popup","livereload"],"styles":{"website":"./styles/website.css"},"pluginsConfig":{"livereload":{},"splitter":{},"search-pro":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"popup":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"favicon":{},"back-to-top-button":{},"pageview-count":{},"expandable-chapters-small":{},"sharing":{"qq":false,"all":["google","facebook","weibo","twitter","qq","qzone","linkedin","pocket"],"douban":false,"facebook":false,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":false,"messenger":false,"line":false,"vk":false,"pocket":false,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"toggle-chapters":{},"expandable-chapters":{}},"theme":"default","author":"hzh","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"计算机 ,java , 大数据 基础知识体系","language":"zh-hans","gitbook":"3.2.3"},"file":{"path":"数据结构/4.排序算法.md","mtime":"2020-12-21T14:44:32.676Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-12-30T11:12:56.611Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-toggle-chapters/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-code/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-livereload/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

